Изогении эллиптических кривых: математические основы

Изогения между двумя эллиптическими кривыми E и E' над полем k — это неконстантное рациональное отображение phi: E -> E', которое также является гомоморфизмом групп — оно переводит групповую операцию на E в групповую операцию на E'. Для каждой изогении phi существует двойственная изогения phi_hat: E' -> E, такая что композиция phi_hat с phi равна умножению на deg(phi) на E. Степень изогении равна размеру её ядра: изогения степени l имеет ядро размера l. Изогении обобщают скалярное умножение: умножение на n — это изогения E в себя степени n^2. Изогении над конечными полями вычисляются как рациональные функции (многочлены), которые можно эффективно вычислять.

Формулы Велу (1971) дают явные формулы для вычисления изогении phi: E -> E/G по заданной подгруппе G группы E. Кривая-образ E/G = E' и рациональное отображение phi полностью определяются группой G. Формулы Велу вычисляют коэффициенты кривой-образа и рациональное отображение как рациональные функции степени, равной |G|. Для подгруппы ядра G простого порядка l изогения имеет степень l и может быть вычислена за O(l) операций. Алгоритмы sqrt-Velu (Bernstein и др., 2019) сокращают это число до O(sqrt(l)) операций при больших l, делая возможными эффективные изогении больших простых степеней в CSIDH. Формулы Велу являются основным вычислительным инструментом всей криптографии на основе изогений.

Эллиптические кривые над конечным полем Fp можно организовать в граф изогений. Вершины — это j-инварианты эллиптических кривых (канонический инвариант, однозначно определяющий кривую с точностью до изоморфизма). Рёбра — это l-изогении: каждая обыкновенная кривая имеет ровно l+1 исходящих l-изогений при малом простом l (что следует из строения подгрупп l-кручения). Граф l-изогений над Fp является (l+1)-регулярным графом. Свойство Рамануджана этих графов (графов-расширителей) означает, что случайные блуждания по ним быстро перемешиваются, обеспечивая предположение о трудности, лежащее в основе криптографии на основе изогений: случайные блуждания длины O(log p) дают равномерные распределения по j-инвариантам.

Эллиптические кривые над Fp делятся на две категории. Обыкновенные кривые имеют нетривиальный p-ранг, то есть существует p^2 классов изоморфизма и сложный граф изогений со структурой вулкана (кратерами и ярусами). Сверхсингулярные кривые имеют p-ранг 0 и все находятся в одном связном графе изогений над Fp2. Количество сверхсингулярных j-инвариантов над Fp приблизительно равно p/12. SIDH и SIKE используют сверхсингулярные кривые, поскольку их граф изогений является графом Рамануджана с сильными свойствами расширения и не имеет структуры вулкана, которая могла бы выдать направление блуждания. CSIDH также использует сверхсингулярные кривые, но над Fp, а не над Fp2, используя другую алгебраическую структуру.

Криптография на основе изогений основывается на двух связанных трудных задачах. Задача о сверхсингулярной изогении (SSIP): по двум сверхсингулярным эллиптическим кривым E и E' над Fp2 найти изогению phi: E -> E'. Задача вычислительной сверхсингулярной изогении (CSSI): по E, E' = phi(E) и степени phi найти phi. Лучший классический алгоритм для SSIP работает за O(p^{1/4}) времени. Лучший квантовый алгоритм (поиск клешни Тани) работает за O(p^{1/6}) времени. При p = 2^{434} это даёт 128-битную классическую безопасность. Это значительно меньшее квантовое ускорение, чем экспоненциальное ускорение алгоритма Шора против RSA/ECC, поэтому схемы на основе изогений считаются постквантово защищёнными.

SIDH (Диффи—Хеллман на основе сверхсингулярных изогений) использует специально устроенное простое число p = 2^a * 3^b - 1, благодаря которому кривая E над Fp2 имеет точки 2^a-кручения (множество точек P, для которых 2^a * P = 0) и доступные точки 3^b-кручения. Секрет Алисы — 2^a-изогения phi_A: E -> E_A, ядро которой порождено случайным элементом 2^a-кручения. Секрет Боба — 3^b-изогения phi_B: E -> E_B. Они обмениваются образами точек кручения: Алиса публикует E_A и phi_A(P_B), phi_A(Q_B). Боб публикует E_B и phi_B(P_A), phi_B(Q_A). Это позволяет каждой стороне вычислить изогении, исходящие из кривой другой стороны, и прийти к одному и тому же общему j-инварианту.

Кольцо эндоморфизмов End(E) эллиптической кривой — это кольцо всех изогений из E в себя, включая скалярные умножения. Для обыкновенных кривых над Fp End(E) является порядком в мнимом квадратичном поле. Для сверхсингулярных кривых End(E) является максимальным порядком в кватернионной алгебре, разветвлённой в p и бесконечности. Структура End(E) полностью определяет кривую с точностью до изоморфизма. Считается, что задача вычисления End(E) по E трудна (для сверхсингулярных кривых она эквивалентна SSIP). Атака Castryck—Decru на SIDH использовала дополнительные сведения, утёкшие из протокола SIDH, чтобы эффективно восстановить часть кольца эндоморфизмов и разрушить схему.

Изогения степени l phi: E -> E' может быть представлена многочленом степени l (или l/2 после оптимизации симметрии с использованием того факта, что у взаимно обратных точек одинаковая x-координата). Вычисление phi(P) для заданной точки P требует O(l) умножений при использовании формул Велу. Для SIDH при l = 2^a, приблизительно равном 2^216, это кажется неприемлемым, но SIDH использует тот факт, что изогении 2^a можно разложить в цепочку из a отдельных 2-изогений: каждая 2-изогения вычисляется дёшево, а цепочка из a шагов даёт 2^a-изогению. Аналогично обрабатываются 3^b. Благодаря sqrt-Velu вычисления больших изогений нечётной простой степени в CSIDH выполняются за O(sqrt(l)), а не за O(l), что делает CSIDH практически применимой.

SIKE (инкапсуляция ключа на основе сверхсингулярных изогений) была кандидатом NIST PQC, который прошёл все раунды до четвёртого, когда его взломали. SIKE отличалась самыми маленькими размерами ключей среди всех кандидатов NIST: 374 байта для SIKEp434 (уровень 1 NIST). Для сравнения, открытые ключи ML-KEM-512 занимают 800 байт. SIKE достигала такой компактности, поскольку общий секрет извлекался из единственного j-инварианта (элемента поля размером около 430 бит). За компактность пришлось заплатить производительностью: SIKE работала в 100–1000 раз медленнее других кандидатов. Когда Castryck и Decru взломали SIKE в июле 2022 года с помощью классической атаки, выполнявшейся на ноутбуке за считанные минуты, SIKE немедленно исключили из конкурса NIST.

Криптография на основе изогений занимает уникальное место среди постквантовых подходов. Размеры ключей: значительно меньше, чем у решёточных схем (ML-KEM: 800 и более байт), или у подписей на основе хеш-функций (SLH-DSA: открытый ключ размером 32–49 байт, но подписи размером 7856–49856 байт). Производительность: значительно ниже, чем у всех альтернатив (SIKE работала в 100–1000 раз медленнее ML-KEM). Криптографическое предположение: отличается от LWE (используется в ML-KEM/ML-DSA), SIS и предположений о стойкости хеш-функций, что обеспечивает криптографическое разнообразие. Основа постквантовой безопасности: для задачи поиска пути по изогениям не известен квантовый алгоритм полиномиального времени, в отличие от RSA/ECC, которые алгоритм Шора полностью взламывает. Классический взлом SIKE показывает, что стойкость изогений всё ещё изучается, в отличие от хорошо исследованной задачи LWE.

Несмотря на взлом SIKE, криптография на основе изогений остаётся активной областью исследований. SQISign (короткие подписи на основе кватернионов и изогений) — схема подписей на основе изогений с подписями размером 177 байт (по сравнению с 2420 байтами у ML-DSA для уровня 2), то есть с самыми короткими из известных подписей PQC. SQISign использует трудную задачу вычисления изогении заданной степени между двумя заданными сверхсингулярными кривыми, формализованную как задача о кольце эндоморфизмов. FESTA (быстрое шифрование на основе атак на сверхсингулярные точки кручения) — новая конструкция KEM, которая избегает дополнительных вспомогательных данных о точках кручения, из-за которых SIDH был уязвим. CTIDH (CSIDH с постоянным временем выполнения) повышает производительность CSIDH. Эти схемы сохраняют актуальность исследований изогений даже после исключения SIKE.

Что такое изогения между эллиптическими кривыми?

Изогения — это рациональное отображение phi: E -> E', являющееся гомоморфизмом групп, причём её степень равна размеру ядра. Формулы Велу вычисляют кривую-образ и отображение по подгруппе ядра. Графы изогений представляют кривые в виде вершин, соединённых рёбрами l-изогений, образующими (l+1)-регулярные графы Рамануджана. Сверхсингулярные кривые (используемые в SIDH/SIKE/CSIDH) имеют графы изогений с сильными свойствами расширения. Задачи SSIP и CSSI лежат в основе безопасности изогений. SIDH использует структуру точек кручения с чередующимися цепочками 2- и 3-изогений. Вычисление кольца эндоморфизмов эквивалентно SSIP. SQISign и FESTA представляют активные направления исследований после SIKE, использующие трудность задачи о кольце эндоморфизмов.