Эксперты лаборатории криптографии российской ИТ-компании «Криптонит» предложили принципиально новый способ оценки защищённости постквантовых систем на линейных кодах. Он позволяет математически выявлять в них некоторые «слабые места» ещё на стадии проектирования и до начала дорогостоящих эмпирических тестов. Результаты работы представил на конференции CTCrypt 2026 зам. руководителя лаборатории криптографии по научной работе Иван Чижов. В своём докладе «Свойства кода квадратичных отношений и его применение в задаче декодирования линейных кодов» он предложил новый взгляд на внутреннюю структуру линейных кодов и выявил ранее незамеченные закономерности, влияющие на криптографическую надёжность.
Почему линейные коды важны в криптографии
В последние годы криптографы ищут алгоритмы, которые сохранят стойкость даже при появлении квантовых вычислителей достаточной мощности. Одним из наиболее перспективных и хорошо изученных направлений остаются криптосистемы, основанные на задачах теории помехоустойчивого кодирования. Исторически первой такой системой стала криптосистема Мак-Элиса, предложенная ещё в 1978 году. Несмотря на почтенный возраст, её модификации и варианты на различных классах линейных кодов до сих пор рассматриваются как перспективные кандидаты в постквантовые стандарты.
Секретность в таких схемах обычно обеспечивается сложностью декодирования случайного линейного кода без знания его специальной структуры. Однако за десятилетия исследований выяснилось, что некоторые классы кодов, первоначально казавшиеся стойкими, содержат скрытые алгебраические зависимости, которые можно использовать для атаки.
Одним из мощных инструментов анализа стала операция произведения Шура — Адамара, или покомпонентного умножения линейных кодов. С её помощью можно строить так называемые «коды квадратичных отношений» — линейные пространства, связанные с квадратичными формами, обращающимися в ноль на столбцах порождающей матрицы кода. Именно эти коды квадратичных отношений позволяют заглянуть «внутрь» криптографической системы и обнаружить потенциальные уязвимости, невидимые при стандартном анализе.
Новый класс уязвимостей и условия их возникновения
В ходе исследования Иван Чижов проанализировал относительно новый подход к построению атак на кодовые криптосистемы. Автором выявлен новый класс уязвимостей — скрытые «слабые места», связанные с поиском квадратичных соотношений специального вида. Показано, что квадратичные формы, обращающиеся в ноль на столбцах порождающей матрицы, всегда существуют в любом коде. Однако среди них лишь некоторые имеют специальный вид, а именно — раскладываются в произведение двух ненулевых линейных форм. Такие формы называются составными. Если в коде квадратичных отношений найти эти составные квадратичные формы, то это создаёт благоприятные условия для атаки: атакующий может попытаться отыскать эти редкие соотношения и применить их для декодирования.
В статье подробно описаны условия, при которых эти слабые места возникают.
Квадратичная форма – это уравнение второй степени, которое обращается в ноль на столбцах порождающей матрицы линейного кода. Иногда уравнение второй степени может быть декомпозировано в совокупность уравнений первой степени. Так, например, уравнение вида x^2-y^2 = 0 можно решить, находя корни двух линейных уравнений: x-y=0 или x+y=0. В этом случае квадратичная функция x^2-y^2 является составной и может быть разложена в произведение (x-y)*(x+y).
«Именно составные квадратичные формы, обнуляющие столбцы порождающей матрицы, представляют наибольший интерес для атакующего. Например, ускоренная атака возможна, если минимальное расстояние кода слишком велико, или если соотношение размерности кода к его длине находится в соотношении примерно 2 к 1. Это существенно уточняет границы параметров для кодовых криптографических схем. В качестве доказательства продемонстрирован алгоритм декодирования, который использует составные квадратичные формы для реализации атак на криптосистемы с различными классами линейных кодов», — пояснил Иван Чижов.
Практическая ценность работы
Исследование позволяет сократить затраты на стандартизацию целого семейства постквантовых алгоритмов, математически выявить в них некоторые потенциальные уязвимости ещё на ранней стадии и точнее подобрать оптимальные параметры постквантовых схем шифрования.
Вместо того чтобы проводить дорогостоящий эмпирический анализ каждого нового варианта криптосистемы на кодах, разработчики могут использовать предложенные в работе критерии для быстрой отбраковки заведомо слабых параметров или классов кодов.
Предложенный им алгоритм декодирования работает в некоторых случаях с меньшими вычислительными затратами, чем многие ранее представленные (Пранга, Штерна, Думера, BJMM и другие).
Возможные сценарии применения в ближайшем будущем
В ближайшие годы ожидается завершение процессов стандартизации постквантовых криптографических алгоритмов в ведущих мировых организациях. Результаты этой работы могут быть непосредственно использованы:
– при анализе стойкости кандидатов на стандарт, основанных на разных классов линейных кодов и их подкодов;
– при разработке новых вариантов на основе криптосистемы Мак-Элиса, где параметры кода (длина, размерность, минимальное расстояние) можно выбирать, исходя из предложенных критериев, заведомо исключая уязвимые варианты.
Кроме того, сам алгоритм декодирования, построенный на поиске составных квадратичных форм, может найти применение в легитимном декодировании при неизвестной структуре кода — например, в системах связи с адаптивным выбором кода, где нет заранее известного эффективного декодера.
Таким образом, работа Ивана Чижова вносит существенный вклад в теорию помехоустойчивого кодирования и постквантовую криптографию, предлагая новые математические критерии оценки стойкости и эффективный инструмент анализа.