Будущее криптографии на основе изогений

Взлом SIKE Castryck-Decru в июле 2022 года полностью изменил область криптографии на основе изогений. До этого криптография на основе изогений считалась перспективным постквантовым направлением: она предлагала небольшие размеры ключей, активно развивалась в рамках стандартизации и привлекала всё больше специалистов. После падения SIKE области пришлось заново проверить свои основы. Главный вопрос звучал так: какие аспекты криптографии на основе изогений остаются трудными после появления новых методов изогений Ришело? По-видимому, сложность на основе колец эндоморфизмов (используемая в SQISign) и коммутативные действия групп классов (CSIDH) остаются неизменными. Уязвимым компонентом оказалась утечка вспомогательных точек кручения, специфичная для SIDH, а не изогении в целом.

SQISign (краткая подпись на кватернионах и изогениях, De Feo et al., 2020) — самая компактная из известных постквантовых схем подписи. Открытый ключ: 64 байта (суперсингулярный j-инвариант). Подпись: 177 байт для уровня 1. Для сравнения, открытые ключи ML-DSA (Dilithium) имеют размер 1312 байт, а подписи — 2420 байт для уровня 2. Безопасность SQISign основана на соответствии Дейринга: задача вычисления изогении заданной степени между двумя данными суперсингулярными кривыми эквивалентна поиску идеала в кватернионной алгебре кольца эндоморфизмов. SQISign использует идентификационную схему Fiat—Shamir для этой трудной задачи, формируя подпись как сжатое представление изогении-ответа.

Компактность SQISign достигается ценой серьёзных потерь производительности. Для создания подписи необходимо вычислить изогению большой степени (примерно p^{1/4}) с помощью преобразования идеала в изогению в кватернионной алгебре — вычислительно затратной операции, занимающей примерно 60–600 секунд на настольном CPU в зависимости от набора параметров. Проверка выполняется быстрее (около 200 мс), но всё равно намного медленнее проверки ML-DSA, занимающей микросекунды. SQISign 2.0 (2023) благодаря улучшениям алгоритма повысил производительность в 100 раз, сократив создание подписи до 1–10 секунд. SQISign HD (высокой степени) и другие варианты продолжают оптимизироваться. Целевое применение — сценарии, в которых объём передаваемых данных крайне ограничен (сертификаты для устройств Интернета вещей, данные блокчейна, космическая связь), а скорость вычислений вторична.

FESTA (быстрое шифрование на основе атак на суперсингулярные точки кручения, 2023) — это KEM, специально разработанный для устранения утечки точек кручения в стиле SIDH. Главная идея конструкции заключается в следующем: вместо публикации phi_A(P_B) и phi_A(Q_B), как в SIDH, FESTA использует другую структуру изогении, в которой открытым ключом шифровальщика служит только кривая-образ (без образов точек кручения). FESTA использует 2^n-изогении изменённым способом, который позволяет расшифровывать сообщение без образов базиса точек кручения другой стороны. Предварительный анализ показывает, что FESTA противостоит атаке Castryck-Decru благодаря другой структуре вспомогательной информации. Это перспективное направление, но оно требует более тщательного криптоанализа: сообщество изогений проявляет осторожность после неожиданного взлома SIKE.

SCALLOP (масштабируемые коммутативные действия с большими ориентированными простыми числами, 2023) устраняет слабое место CSIDH в отношении квантовой стойкости. Небольшое простое число p длиной 512 бит в CSIDH обеспечивает лишь около 65 бит квантовой стойкости из-за субэкспоненциального алгоритма Kuperberg. SCALLOP использует другую алгебраическую структуру: кривые с комплексным умножением из больших мнимых квадратичных порядков, где группа классов специально сконструирована для противодействия квантовым атакам в стиле Kuperberg. SCALLOP достигает большей эффективной группы классов; его параметры обеспечивают 128-битную квантовую стойкость при меньших размерах параметров, чем CSIDH-5000. Обратная сторона заключается в том, что алгебраическая конструкция SCALLOP сложнее и получила меньше независимого анализа, чем CSIDH.

Учитывая уникальную компактность схем на основе изогений (подписи SQISign размером 177 байт и ключи CSIDH размером 64 байта) и отличающиеся от решёточных схем предположения об их сложности, гибридные конструкции объединяют компоненты на основе изогений и решёток для многоуровневой защиты. Гибридный KEM: инкапсулировать секрет с помощью ML-KEM-512 AND с помощью CSIDH-512, а затем вычислить хеш от обоих секретов. Для получения комбинированного ключа потребуется взломать одновременно и ML-KEM (сложность LWE), и CSIDH (действие группы классов). Если хотя бы одна из этих систем остаётся невзломанной, гибридная схема безопасна. Этот подход криптографической гибкости рекомендован NIST и NSA организациям, которым нужна дополнительная гарантия сверх стойкости любого отдельного постквантового примитива, особенно при неопределённости сроков появления квантовых компьютеров.

Доказательства с нулевым разглашением на основе изогений — новое направление исследований. Задача поиска пути изогений (найти phi: E -> E', если обе кривые известны) может служить трудной задачей для схем доказательства знания. Протоколы Sigma для «Я знаю изогению из E в E'» позволяют пройти аутентификацию, не раскрывая изогению. Vero (2022) демонстрирует практическую систему доказательств с нулевым разглашением на основе изогений. Такие доказательства ZK естественно компактны (утверждение состоит всего из двух j-инвариантов), но пока слишком медленны для практического внедрения. По мере совершенствования вычисления изогений доказательства с нулевым разглашением на их основе могут стать альтернативой доказательствам на основе решёток или хеш-функций в тех случаях, когда важно разнообразие оснований стойкости.

Методы изогений важны не только для постквантовой криптографии — они применяются и в классической криптографии на эллиптических кривых. Алгоритм Schoof-Elkies-Atkin (SEA) для подсчёта точек на эллиптических кривых использует изогении для вычисления следа Фробениуса, что позволяет эффективно создавать параметры безопасных эллиптических кривых. Изогении используются в усовершенствованиях метода ро Полларда для вычисления ECDLP. Метод CM (комплексного умножения) для построения кривых с заданным порядком использует полиномы классов, которые по сути являются объектами изогений. Инструменты криптоанализа на основе изогений (поиск путей изогений гладкой степени) применяются для оценки предложенных параметров эллиптических кривых на наличие скрытых лазеек — это напрямую связано с проблемой Dual EC DRBG.

По состоянию на 2024 год ни одна схема на основе изогений не стандартизирована NIST или другими крупными организациями. В рамках процесса стандартизации PQC NIST стандартизировал ML-KEM, ML-DSA, SLH-DSA и FN-DSA — все они основаны на решётках или хеш-функциях. NIST проводит второй раунд оценки подписей PQC; SQISign подан на рассмотрение, но вызывает опасения из-за производительности. Сообщество изогений работает над более зрелой версией SQISign 3.0 с практичным временем создания подписи (цель — менее секунды). ISO и ETSI пока не стандартизировали ни одной схемы на основе изогений. Наиболее вероятный путь стандартизации в ближайшей перспективе — SQISign для нишевых приложений, которым нужны минимальные размеры подписей, возможно, в качестве информационного, а не обязательного стандарта. Широкое внедрение требует улучшения производительности на порядок.

Активные направления исследований в криптографии на основе изогений по состоянию на 2024 год: (1) варианты SQISign (SQISign 2.0, HD, Fast SQISign), повышающие производительность создания подписей и приближающие её к работе менее чем за секунду; (2) анализ квантовой стойкости CSIDH и его вариантов — уточнение оценок атаки Kuperberg и поиск алгебраических структур, устойчивых к ней; (3) новые предположения о сложности — вычисление колец эндоморфизмов суперсингулярных кривых и задачи на модули над мнимыми квадратичными кольцами; (4) изогении на основе псевдослучайных функций со скрытым вычислением и их применения в протоколах с сохранением конфиденциальности; (5) аппаратные реализации арифметики изогений — использование параллелизма FPGA для действия группы классов CSIDH; (6) интеграция действий групп на основе изогений с универсальными криптографическими платформами для действий групп при создании новых схем функционального шифрования и схем на основе атрибутов.

Взлом SIKE может навести на мысль о полном отказе от криптографии на основе изогений. Однако криптографическое сообщество придерживается противоположной позиции: этот взлом оказался ценным именно потому, что выявил, какие структуры небезопасны (утечка точек кручения в SIDH), а какие по-прежнему трудно взламывать (кольца эндоморфизмов, действия групп классов). Изучение изогений по-прежнему важно по следующим причинам: (1) разнообразие постквантовой криптографии — наличие предположений о безопасности не только на основе решёток снижает системный риск, если LWE будет взломана; (2) SQISign предоставляет исключительно компактные подписи, которым пока нет аналогов; (3) методы изогений помогают развивать криптоанализ эллиптических кривых и проверять параметры; (4) эта математика красива и плодотворна — инструменты, разработанные для взлома SIKE, значительно улучшили понимание колец эндоморфизмов эллиптических кривых, используемых в других областях.

Какое предположение о вычислительной трудности лежит в основе подписей SQISign?

После взлома SIKE в 2022 году криптография на основе изогений продолжает развиваться благодаря другим предположениям о вычислительной трудности. SQISign предоставляет постквантовые подписи размером 177 байт — самые компактные из известных, — основанные на вычислительной трудности, связанной с кольцами эндоморфизмов; производительность улучшается, а цель — добиться времени выполнения менее секунды. FESTA разработан с учётом утечки точек кручения в SIDH при создании схем инкапсуляции ключа. SCALLOP нацелен на 128-битную квантовую стойкость с помощью ориентированных кривых. Гибридные схемы на основе изогений и решёток обеспечивают разнообразие предположений о безопасности. В настоящее время ни одна схема на основе изогений не стандартизирована. Стандартизация SQISign — наиболее вероятный путь в ближайшей перспективе. Взлом SIKE углубил понимание того, что именно необходимо скрывать в протоколах на основе изогений, и привёл к появлению новых математических инструментов, используемых во всей криптографии эллиптических кривых.