Аннотации

В 2026 году исполняется ровно 50 лет с публикации фундаментальной статьи Диффи и Хеллмана, с которой началась новая эра развития криптографии вообще и такого класса протоколов как протоколы выработки общего аутентифицированного ключа. С тех пор было предложено несколько сотен различных протоколов, обладающих разными свойствами и основывающихся на разных криптографических примитивах. В докладе будет рассказано о большом обзоре известных AKE-протоколов и выработанном авторами общем подходе к их единообразному описанию. Также будет приведен систематизированный обзор тех возможностей нарушителя и угроз, которые рассматривались в ходе криптографического анализа таких протоколов. В заключение будут описаны атаки, использующие некоторые нестандартные возможности нарушителя, на ряд классических и довольно новых протоколов, в частности, на протоколы семейства SIGMA.

Постквантовая криптография (PQC) широко признана основным решением для защиты от квантовых атак на классическую криптографию с открытым ключом. В настоящее время значительные усилия сосредоточены на переводе систем с RSA и ECC на стандартизованные алгоритмы PQC. Однако замена криптографических алгоритмов не гарантирует автоматически долгосрочную безопасность. Многие критически важные системы должны оставаться заслуживающими доверия на протяжении нескольких десятилетий, в течение которых криптографические стандарты, якоря доверия, нормативные требования и операционные инфраструктуры неизбежно будут развиваться. В этом докладе мы вновь обращаемся к понятию долгосрочной безопасности за пределами традиционного нарратива миграции на постквантовую криптографию. На примере систем удалённой подписи как показательного кейса мы рассматриваем проблемы, связанные с долгосрочной проверкой, сохранением меток времени, управлением жизненным циклом сертификатов, архивной валидацией и непрерывностью доверия на протяжении нескольких поколений криптографических переходов. Мы утверждаем, что криптографическая гибкость — необходимое, но недостаточное условие долгосрочной безопасности. Главная задача — поддерживать проверяемое доверие, несмотря на непрерывные технологические и организационные изменения. Мы обсуждаем направления будущих исследований в области управления жизненным циклом доверия в эпоху после PQC.

Схема групповой подписи позволяет некоторой группе участников анонимно подписывать сообщения от имени группы, тогда как назначенный уполномоченный орган может при необходимости отозвать анонимность, чтобы обеспечить подотчётность пользователей. В этом докладе я представляю постквантовую полностью динамическую схему групповой подписи под названием DGSP, построенную только на симметричном шифровании и хэш-функциях. DGSP обеспечивает следующее: (i) время инициализации практически не зависит от числа подписей, которые могут быть выпущены, с поддержкой до 2⁶⁴ подписей; (ii) алгоритм отслеживания, выполняемый уполномоченным органом, имеет постоянное время работы, не зависящее от числа участников; (iii) множество участников является полностью динамическим, и участников можно удалять или добавлять по мере необходимости без общесистемных обновлений; и (iv) прямую анонимность, при которой, если секреты пользователя скомпрометированы, их нельзя использовать для деанонимизации предыдущих подписей. DGSP — первая схема групповой подписи, основанная только на симметричных примитивах, которая достигает всех этих свойств: предыдущее передовое решение в этой области SPHINX-in-the-Head (SITH), которое не достигает (ii) или (iv), и DGMT, которое не достигает (i) и может не достигать (iv). Как DGMT, но в отличии от SITH, DGSP является схемой с сохранением состояния, и участники должны обновлять локальное хранилище «сертификатов», чтобы выпускать новые подписи. Подписи DGSP примерно в 5 раз больше, чем у DGMT, но почти в 100 раз меньше, чем у SITH, а все базовые операции выполняются менее чем за 2 миллисекунды. Мы доказываем безопасность в стандартной модели при стандартных предположениях для симметричных примитивов. DGSP is a compelling solution for applications requiring large-scale user support, efficient operations, and conservative post-quantum security. GSP является подходящим решением для систем, требующих поддержки большого числа участников, эффективных операций и консервативной постквантовой безопасности.

Криптографическая гибкость подразумевает, что различные криптографические примитивы могут быть заменены в рамках протокола на аналогичные. В докладе обсуждаются требования, которым должен удовлетворять криптоанализ этих примитивов. Делается вывод, что истинная криптографическая гибкость требует автоматизированного криптоанализа — подхода, который является воспроизводимым, проверяемым и чётко определяет область своей применимости.

В докладе рассматривается комбинаторно-геометрическая задача разбиения конечномерных векторных пространств над конечным полем на непересекающиеся аффинные подпространства заданной размерности. Исследуются структурные свойства таких разбиений: получены оценки на их общее количество, предложены алгоритмы эффективного построения с использованием линейных преобразований и рекурсивных конструкций, а также затронута проблема эффективного порождения и нумерации для целей перебора и классификации. Особое внимание уделяется дополнительным ограничениям, таким как попарная ортогональность направляющих подпространств и отсутствие векторов, ортогональных большому числу аффинных подпространств из разбиения. Обсуждаются криптографические приложения: показано, как специальные виды таких разбиений могут быть использованы для конструирования бент-функций (максимально нелинейных булевых функций); представлены идеи по построению криптостойких S-боксов для алгоритмов симметричного шифрования. Также предлагаются подходы к оценке устойчивости к дифференциальному и линейному криптоанализу и влияния структуры разбиения на вычислительную сложность реализации, что позволяет намечать пути оптимизации баланса между производительностью и стойкостью.

Криптосистема Мак-Элиса, представленная в 1978 году и основанная на двоичных кодах Гоппы, является старейшей схемой шифрования с открытым ключом, всё ещё считающейся стойкой к квантовым атакам. Её замечательная долговечность частично объясняется кажущейся сложностью отличения открытого ключа Мак-Элиса от случайного линейного кода. В этом докладе я опишу простой классический квазиполиномиальный различитель для схемы Мак-Элиса на кодах Гоппы в асимптотическом режиме, лежащем в основе Classic McEliece. Для кода длины n, алгоритм работает за время n^{O(log n)} и отличает открытый ключ Мак-Элиса от равномерно случайного двоичного линейного кода с преимуществом 1-o(1). Атака не является чисто асимптотической: она применима ко всем наборам параметров Classic McEliece, рассматриваемым в процессе NIST, и даёт улучшенные, хотя всё ещё далёкие от практических, конкретные оценки атаки. Интересно, что атака возникла из неудачной попытки построить дважды эффективные схемы конфиденциального извлечения информации (PIR) на основе алгебраических локально декодируемых кодов. Я поясню различитель через эту PIR перспективу, что даёт относительно интуитивное представление об эксплуатируемой структуре. В заключение я обсужу эвристические расширения различителя до квазиполиномиального времени расшифрования шифртекста и восстановления ключа. Атака восстановления ключа, в частности, остаётся структурно близкой к различителю и может иметь последствия для конкретных оценок безопасности Classic McEliece. Это совместная работа с Ювалем Ишаем, Ааюшем Джайном и Ночжоу Суном.

Криптосистема Мак-Элиса на двоичных кодах Гоппы — старейшая схема с открытым ключом, долгое время считавшаяся стойкой как к классическим, так и к квантовым атакам. Недавно Гошал, Ишай, Джайн и Сунь построили квазиполиномиальный алгоритм, отличающий публичные ключи схемы Мак-Элиса от случайных матриц. В докладе будут представлены два способа развить этот различитель до алгоритма восстановления эквивалентного секретного ключа. Первая атака основана на глубоком восстановлении касательных пространств скрытой кривой для относительно небольшого числа позиций, а затем на поиске подходящей кривой с помощью линейной алгебры. Вторая атака строит касательные пространства первого порядка для всех позиций, затем по ним вычисляет минорный код, который оказывается полным ОРС-кодом; к этому коду далее применяется стандартная атака Сидельникова–Шестакова. Обе атаки полностью проверены на кодах Гоппы над GF(4); для двоичных кодов Гоппы прямая проверка вычислительно недоступна, поэтому применимость атак опирается на дополнительные структурные и эвристические предположения. Для них мы представим некоторые косвенные подтверждения. При выполнении сформулированных предположений оценки трудоёмкости атак оказываются значительно ниже заявленных уровней стойкости Classic McEliece.

В этом докладе мы представим последние достижения в области алгебраических атак на семейство криптосистем UOV, включая атаку на основе альтернативной алгебры, атаки на основе симметрической алгебры и другие новые атаки. Мы объясним детали этих атак и связанные с ними проблемы.

Мы предлагаем новый подход в криптоанализе, основанный на развитии концепции комбинаторной эквивалентности. Цель — переписать криптосистему в комбинаторно эквивалентной форме, чтобы выявить новые свойства, которые позволяют лучше различать секретный ключ, используемый при шифровании. Мы успешно применили этот подход к наиболее стойкой на сегодняшний день категории поточных шифров. Сначала мы определяем концептуальный шифр под названием Cipherbent6, который охватывает большинство трудностей криптоанализа поточных шифров. Мы значительно превзошли все известные методы криптоанализа. Мы применили этот подход к шифру Achterbahn и снова получили значительно лучшие результаты криптоанализа.

Мы рассматриваем последовательность случайных конечных автоматов ℵ_n(X, Q_n, Y, F_n, Phi_n) с конечными входными X и выходными Y алфавитами, растущим числом |Q_n| = n внутренних состояний и функций выхода и перехода состояний f_n,t, φ_n,t в каждом такте t автоматов, выбранных случайным образом из наборов функций F_n и Φ_n. Доказана возможность асимптотической локальной инверсии автомата ℵ_n. А именно, значение x_n,t входной последовательности {x_n,t}_t=1^T автоматов в момент времени t, при T, t, n → ∞, так что √n = o(min(t, T−t)), с вероятностью не менее 1/3 может быть восстановлено из известной выходной последовательности {y_n,t}_t=1^T и известны последовательности функций {φ_n,t}_t=1^T и {f_n,t}_t=1^T.

1. Определение тех булевых функций, сужения которых на аффинные пространства являются платообразными (совместная работа с Дэррионом Торнбургом) Квадратичные булевы функции (то есть булевы функции алгебраической степени не выше 2), бент-функции (т.е. максимально нелинейные булевы функции от чётного числа переменных) и, как мы покажем, частично бент-функции (т.е. аффинные расширения бент-функций на линейные суперпространства) обладают сильным свойством: все их сужения на аффинные гиперплоскости являются платообразными (т.е. имеют преобразование Уолша, принимающее значения из множества вида {0, ±λ}, где λ — это положительное целое число, называемое амплитудой). Мы определяем для любых n и k < n класс Cⁿ_k тех булевых функций от n переменных, сужения которых на все k-мерные аффинные подпространства 𝔽₂ⁿ являются платообразными (любой амплитуды). Мы характеризуем частично бент-функции (соответственно, квадратичные булевы функции) как те функции, которые являются платообразными на любой аффинной гиперплоскости (соответственно, на любом аффинном подпространстве размерности k, где 3 ≤ k ≤ n−2, тогда как при 0 ≤ k ≤ 2 это все булевы функции). Это даёт новую характеристику частично бент-функций и иерархию среди булевых функций от n переменных из шести вложенных классов, каждый из которых, для любого n ≥ 5, оказывается строго включённым в следующий: квадратичные функции, частично бент-функции, сужения частично бент-функций от (n+1) переменной на 𝔽₂ⁿ, платообразные функции, сужения платообразных функций от (n+1) переменной на 𝔽₂ⁿ, и все булевы функции. Мы оставляем открытыми две проблемы — точное определение третьего и пятого из этих классов, — но начинаем изучение первого из этих двух классов, характеризуя ситуацию, когда платообразная функция g имеет сужение f на аффинную гиперплоскость H, которое является платообразным. Мы также характеризуем, когда g является частично бент-функцией. Наша характеристика частично бент-функций (соответственно, квадратичных функций) распространяется на сильно платообразные векторные функции. 2. Понятие об S-боксах для частичной устойчивости к некоторым интегральным атакам Недавно было введено понятие свободы от сумм k-го порядка для векторной функции F: 𝔽₂ⁿ → 𝔽₂^m, обобщающее понятие почти совершенной нелинейности (которое соответствует k = 2) и имеющее некоторое отношение к стойкости к интегральным атакам на блочные шифры за счёт предотвращения распространения свойства деления k-мерных аффинных пространств. Мы покажем, что это понятие, которому векторные функции удовлетворяют редко, можно ослабить, сохранив то же поведение по отношению к свойству деления. Это приводит нас к понятию k-го порядка t-степенной свободы от сумм, сила которого убывает с ростом t и которое совпадает со свободой от сумм k-го порядка при t = 1: для каждого k-мерного аффинного пространства A существует неотрицательное целое число j с весом 2 не более t такое, что ∑_{x ∈ A} (F(x))^j ≠ 0, где F(x) рассматривается в поле 𝔽₂^m. Мы показываем, что t всегда можно взять меньшим или равным min(k, m) при некотором «разумном» условии на F (которому, в частности, удовлетворяют все инъективные функции). Это делает новое понятие более интересным как теоретически, так и практически, чем свобода от сумм (которая является понятием «всё или ничего» и которая на практике дисквалифицирует почти все функции). Параметр t в новом понятии более точно количественно описывает поведение любой «разумной» функции. Достоинством этого параметра является его простота. Мы также показываем, что t больше или равно k / deg(F), где deg(F) — алгебраическая степень F, и выводим две другие нижние границы. Мы изучаем степенные функции, для которых доказываем верхние оценки. Среди них мы изучаем функцию мультипликативного обращения (используемую в качестве S-бокса в AES), для которой мы характеризуем k-го порядка t-степенную свободу от сумм через коэффициенты полиномов подпространств k-мерных векторных подпространств (выводя точное минимальное значение t, когда k делит n) и доказываем, что её k-го порядка t-степенная свобода от сумм эквивалентна её (n−k)-го порядка t-степенной свободе от сумм.

В схеме аутентифицированного шифрования подписывающий подписывает сообщение для конкретного проверяющего, используя свой собственный закрытый ключ и открытый ключ проверяющего. Проверяющий восстанавливает исходное сообщение из подписанного зашифрованного сообщения, используя открытый ключ подписывающего и свой собственный закрытый ключ. Значительная работа в этом направлении выполнена авторами Чжэном и другими. В этом докладе я сначала опишу схему аутентифицированного шифрования для подписи сообщений фиксированной длины блока, основанную на варианте схемы шифрования Эль-Гамаля. Затем я рассмотрю вариант схемы подписи Эль-Гамаля над большими простыми модулями. Наконец, я представлю ещё одну схему аутентифицированного шифрования, которую можно адаптировать для генерации подписей для сообщений произвольной длины.

Криптографическая гибкость зависит от отделения функциональности, требуемой протоколом, от криптографических примитивов, используемых для её обеспечения. Пороговое гомоморфное шифрование традиционно проектировалось тесно связанным образом: схема гомоморфного шифрования напрямую объединяется с разделением секрета, а улучшения эффективности часто вводят ограничения на пространство сообщений, выбор порога или доступность участников. В этом докладе представлен модульный подход к проектированию для разрешения этой дилеммы эффективности и полезности. Подход вводит два модульных интерфейса. Адаптер пространства сообщений (MeSA) отделяет совместимость пространства сообщений от порогового шифрования, тогда как приближённое разделение секрета (ApproxSS) охватывает зашумлённое восстановление, требуемое пороговым FHE. Инстанцирование этих интерфейсов с помощью шифрования на решётках и зашифрованных долей даёт схемы с низкой сложностью, гибким выбором порога и динамическими участниками. Прототипы, протестированные с участием до тысячи сторон, демонстрируют их практическую масштабируемость. В более широком смысле эти результаты показывают, как криптографические узкие места могут быть изолированы за стабильными интерфейсами, позволяя отдельным компонентам развиваться без перепроектирования всего протокола.

В настоящее время наблюдается активное развертывание сетей квантового распределения ключей (КРК) различными исследовательскими группами и коммерческими компаниями по всему миру. В результате формируется разрозненная инфраструктура: множество изолированных «островков» квантовой связи (сегментов), которые часто пересекаются географически, но не взаимодействуют технологически. Возникает острая необходимость в переходе от локальных сетей к глобальной квантовой межсети (Quantum Internetwork). При этом интеграция разнородных сетей в единую экосистему поднимает ряд фундаментальных проблем безопасности, которые являются предметом данного доклада. В момент выработки и распределения ключей для пользователей, подключенных к разным сегментам, неизбежна передача криптографически опасной информации через узлы разных сегментов. В работе рассматриваются способы построения и сценарии функционирования квантовой межсети и исследуются криптографические качества ключей, получаемых в каждом случае.

В докладе рассматриваются ФДСЧ, использующие в качестве источника случайности физический процесс, который может быть описан с помощью теории процессов восстановления, и извлекающие случайность посредством взятия по заданному модулю числа моментов восстановления, приходящихся на равные временные интервалы. Для таких ФДСЧ в докладе дана оценка степени отклонения распределения вырабатываемых значений от равновероятного, которая может быть использована при оценивании практической секретности формируемых криптографических ключей.

В докладе представлен анализ алгоритмов ГОСТ 28147-89, Магма, SIMON, SPECK методом инвариантных подпространств. Исследовано влияние операций ADD, AND, ROTATE на различные классы подпространств. Показано влияние выбора S-блоков (алгоритмы ГОСТ 28147-89 и Магма) и раундовых констант (алгоритмы SIMON и SPECK) на возможность проведения атаки.

В докладе приводится обзор свежих результатов и достижений в области постквантовой криптографии и квантовых вычислений. Дается оценка влияния этих результатов на симметричные криптографические алгоритмы, безопасность которых рассматривается в моделях классов Q1 и Q2. Работа является продолжением представленного на AgileCrypto’25 доклада о результатах квантового криптоанализа режимов работы блочных шифров.

Квантовые вычисления представляют угрозу для классической криптографии с открытым ключом, поэтому крайне важно разрабатывать постквантовые альтернативы, а также методы повышения их безопасности в долгосрочной перспективе. В рамках текущих процессов по стандартизации алгоритмов на основе решеток большее внимание уделяется схемам типа MLWE (наиболее известным примером является ML-KEM), в то время как схемы типа NTRU c нашей точки зрения обладают значимыми конкурентными преимуществами, включая (отчасти) более компактные размеры параметров (в частности, более короткие шифртексты, что важно при ограниченной пропускной способности канала), а также более длительную историю криптоанализа. В настоящем докладе предлагается схема шифрования с открытым ключом (PKE) «Настурция» (Nasturtium), следующая парадигме схем типа NTRU, а также основанный на ней механизм инкапсуляции ключей (KEM). В схеме используется кольцо по простому модулю (триномиальное циклотомическое), пригодное для быстрого умножения многочленов с применением преобразования Фурье, и ряд специальных модификаций для ускорения основных процедур. Обосновывается выбор конструкции, приводятся ее параметры для целевого уровня стойкости 128/256 бит, а также показывается, что схема сопоставима (или несколько превосходит) по стойкости, скорости и размерам параметров с другими схемами на основе решеток, в частности, ML-KEM. Конструкция также предоставляет расширенный (относительно стандартного) интерфейс KEM, который позволяет передавать дополнительную информацию (например, контекст сеанса) для обеспечения привязки вырабатываемого ключа к данному контексту, что может быть полезно в определенных протоколах. Для повышения гибкости и обеспечения дополнительной стойкости схемы рассматриваются способы ее гибридизации с классическим механизмом Диффи-Хеллмана. Базовая и гибридная схемы позволяют выбирать конфигурации под различные целевые свойства безопасности (CPA или CCA), т.е. использовать более производительный вариант (без выполнения хэширования в KEM) в сценариях, где достаточно защиты от CPA-атак (таких как, например, протокол TLS с эфемерными ключами и взаимной аутентификацией участников), либо более устойчивый вариант, если необходимо обеспечить защиту от CCA-атак (например, при использовании статических ключей или более сильных моделей нарушителя).