CSIDH: коммутативные сверхсингулярные изогении

CSIDH (коммутативный сверхсингулярный изогенный протокол Диффи—Хеллмана, Кастрик и др., 2018) — обмен ключами на основе изогений, который полностью избегает утечки через точки кручения SIDH благодаря принципиально иной алгебраической структуре. CSIDH работает со сверхсингулярными кривыми над Fp, а не над Fp2, как SIDH. Предположение о трудности задачи основано на коммутативности действия группы классов: каждая из двух сторон применяет секретный элемент группы классов к общей исходной кривой, а коммутативность гарантирует получение одной и той же общей кривой. Дополнительные сведения о точках кручения не публикуются — открытый ключ представляет собой всего один j-инвариант. Эта конструкция не пострадала от атаки Кастрика—Декрю на SIDH.

Над Fp при p = 3 mod 4 сверхсингулярные кривые E имеют выделенный эндоморфизм pi (эндоморфизм Фробениуса), а их алгебра эндоморфизмов содержит мнимый квадратичный порядок Z[pi]. Группа классов идеалов Cl(Z[pi]) действует свободно и транзитивно на множестве сверхсингулярных кривых над Fp с точностью до изоморфизма. Идеал a из Cl(Z[pi]) действует на кривую E, порождая новую кривую a * E, которая вычисляется как кривая E/E[a], где E[a] — подгруппа кручения, соответствующая идеалу a. Это действие коммутативно: a * (b * E) = b * (a * E) = [ab] * E. Это действие группы CSIDH, обеспечивающее коммутативный аналог Диффи—Хеллмана.

Обмен ключами CSIDH выполняется следующим образом. Открытые параметры: сверхсингулярная кривая E0 над Fp и небольшие нечётные простые числа l_1, ..., l_n. Секретные ключи: Алиса выбирает a = (a_1, ..., a_n), где каждый a_i принадлежит {-m, ..., m} (случайные небольшие целые числа). Боб выбирает b = (b_1, ..., b_n). Открытый ключ Алисы: E_A = [l_1^a_1 * ... * l_n^a_n] * E0. Открытый ключ Боба: E_B = [l_1^b_1 * ... * l_n^b_n] * E0. Общий секрет: Алиса применяет свои секретные показатели степени к E_B, а Боб применяет свои к E_A. Коммутативность гарантирует, что оба получают E_AB = [product(l_i^(a_i + b_i))] * E0. Общий секрет — это j(E_AB). Дополнительные точки не публикуются.

Эталонная реализация CSIDH использует p = 4 * l_1 * l_2 * ... * l_74 - 1, где l_1–l_74 — первые 74 нечётных простых числа (3, 5, 7, ..., 373). В результате p имеет размер примерно 512 бит. Каждая составляющая секретного ключа a_i принадлежит {-5, ..., 5} (11 вариантов для каждой из 74 составляющих). Порядок группы классов примерно равен sqrt(p), а размер пространства ключей составляет 11^74. На каждом шаге вычисления изогении для простого числа l_i находят подгруппу l_i-кручения и вычисляют l_i-изогению по формулам Велу. При использовании sqrt-Velu вычисление каждой изогении для большого простого числа требует O(sqrt(l_i)) операций. Весь обмен ключами занимает примерно 1–5 мс на современном оборудовании для CSIDH-512.

Исходная версия CSIDH не работает за постоянное время: число шагов Велу зависит от значений секретного ключа a_i, раскрывая информацию через побочные каналы по времени. CTIDH (изогенный протокол Диффи—Хеллмана с постоянным временем, Бернштейн и др., 2021) устраняет эту проблему с помощью формата ключа с фиксированным весом и тщательно спроектированного вычисления изогений с постоянным временем. Секретные ключи CTIDH ограничены векторами, для которых сумма абсолютных значений фиксирована (например, sum |a_i| = 130). Вычисление изогении выполняется за фиксированное число шагов независимо от значений секретного ключа; для заполнения шагов, в которых секретный показатель степени равен нулю, используются фиктивные вычисления изогений. CTIDH обеспечивает безопасность, сопоставимую с CSIDH-512, и строгие гарантии постоянного времени, подходящие для развертывания во встраиваемых системах.

Квантовая стойкость CSIDH имеет больше нюансов, чем стойкость схем на основе решёток. Наилучшая квантовая атака использует алгоритм Kuperberg (2005) для задачи скрытого сдвига, который нарушает структуру действия группы классов за субэкспоненциальное время L(1/2) = exp(O(sqrt(log p))). Это существенно эффективнее классической наилучшей атаки за sqrt(p), то есть квантовые компьютеры значительно ослабляют CSIDH по сравнению с классическими атаками. Для 128-битной постквантовой стойкости (против атаки L(1/2)) CSIDH требует простого числа p длиной примерно 5000 бит (CSIDH-5000) — по сравнению с 512 битами для 128-битной классической стойкости. Стойкость CSIDH-512 к квантовым атакам оценивается всего в 62–72 бита, что значительно ниже требований NIST уровня 1.

Безопасность CSIDH опирается на обратную задачу действия группы (GAIP): если даны E_A = a * E0 и E0, необходимо найти a. Наилучший из известных алгоритмов использует сокращение, подобное алгоритму Полига—Хеллмана, в сочетании с методом «малого шага — большого шага»; его классическая сложность составляет O(sqrt(|Cl|)) ~ O(p^{1/4}). Квантовая сложность этой задачи (Kuperberg) делает CSIDH менее стойким к квантовым атакам, чем схемы на основе LWE. Наилучшая квантовая атака на LWE (решёточное просеивание) обеспечивает более консервативный запас стойкости. Преимущество CSIDH — компактность: открытые ключи CSIDH-512 имеют размер 64 байта (только j-инвариант), тогда как ключи ML-KEM-512 занимают 800 байт. Для приложений, которым нужны минимально возможные ключи и допустим меньший запас квантовой стойкости, CSIDH по-прежнему представляет интерес.

Несколько вариантов CSIDH устраняют его ограничения по квантовой стойкости. BSIDH (B — от слова «лучше») использует базовые кривые большей степени и произведения эллиптических кривых, чтобы увеличить размер группы классов, сохранив высокую скорость вычислений. Csurf (CSIDH на поверхности) работает с другим набором суперсингулярных кривых, что позволяет ускорить вычисление действия группы. В предложениях по CSIDH на кривых более высокого рода используются якобианы кривых рода 2 над Fp, что даёт большее пространство действия группы и потенциально повышает запас квантовой стойкости. Ни один из этих вариантов не получил широкого распространения и не рассматривался NIST, отчасти потому, что анализ квантовой стойкости вариантов CSIDH всё ещё развивается и менее проработан, чем для схем на основе решёток.

CSIDH и SIDH различаются по фундаментальным свойствам. Коммутативность: CSIDH использует коммутативное действие группы (группу классов), а SIDH — неинтерактивный обмен ключами на основе некоммутативных изогений со вспомогательными точками кручения. Базовое поле: CSIDH работает над Fp, а SIDH — над Fp2 (квадратичным расширением). Размер открытого ключа: CSIDH — 64 байта (один j-инвариант над Fp), SIDH — 324 и более байт (кривая и две точки над Fp2). Безопасность: CSIDH пережил атаку Castryck-Decru, а SIDH был взломан. Квантовая стойкость: для 128-битной квантовой стойкости CSIDH требует простых чисел длиной 5000 бит; до классического взлома SIDH обеспечивал сопоставимую стойкость к квантовым атакам. Производительность: CSIDH-512 работает примерно за 1–5 мс; SIDH имел сопоставимую скорость, но CSIDH-5000 был бы намного медленнее.

Коммутативность CSIDH делает возможным неинтерактивный обмен ключами (NIKE): Alice публикует E_A = a * E0, а Bob публикует E_B = b * E0. Позднее, без какого-либо дополнительного обмена данными, любой может вычислить общий секрет из любого открытого ключа: Alice вычисляет a * E_B = a * (b * E0) = ab * E0, а Bob вычисляет b * E_A = b * (a * E0) = ab * E0. Это свойство NIKE ценно для приложений, в которых интерактивный обмен ключами непрактичен, например для шифрования электронной почты, когда отправитель и получатель не находятся в сети одновременно. NIKE на основе CSIDH аналогичен NIKE Диффи—Хеллмана, но обеспечивает постквантовую стойкость. ML-KEM (на основе LWE) не поддерживает NIKE естественным образом без дополнительной разработки протокола.

CSIDH не стандартизирован и пока не внедрён в рабочие системы. Это активное направление исследований, для которого доступны реализации: CTIDH (с постоянным временем выполнения), csidh-reference (Python, для обучения) и supersingular-isogeny-toolbox (оптимизированная реализация на C). Главное препятствие для внедрения — квантовая стойкость: оцениваемые 62–72 бита квантовой стойкости CSIDH-512 ниже уровня 1 NIST (128 бит), поэтому он не подходит для постквантовых приложений, требующих соответствия стандартам NIST. CSIDH-5000 достиг бы требуемого уровня стойкости, но работал бы значительно медленнее. Исследования продолжаются: изучается квантовая стойкость и разрабатываются варианты, способные сократить этот разрыв, однако по состоянию на 2024 год CSIDH остаётся исследовательским прототипом, а не готовым к внедрению примитивом.

Почему коммутативное действие группы классов в CSIDH делает возможным неинтерактивный обмен ключами?

CSIDH использует коммутативное действие группы классов Cl(Z[pi]) на суперсингулярных кривых над Fp, где pi — эндоморфизм Фробениуса. Открытые ключи представляют собой отдельные j-инварианты размером 64 байта. Вспомогательные точки кручения не публикуются, что позволяет избежать уязвимости SIDH. Коммутативность действия группы классов делает возможным NIKE. Наилучшая классическая атака имеет сложность O(p^{1/4}), а наилучшая квантовая атака (Kuperberg) выполняется за субэкспоненциальное время L(1/2), поэтому для 128-битной квантовой стойкости требуются простые числа длиной 5000 бит. CTIDH предоставляет реализацию с постоянным временем выполнения. CSIDH-512 имеет всего около 65 бит квантовой стойкости. CSIDH не стандартизирован; исследования сосредоточены на вариантах, повышающих стойкость к квантовым атакам при сохранении компактных ключей.