«Прошло почти двадцать лет, но криптография на основе кодов так и не смогла занять центральное место. Почему? Дело не только в больших ключах и медленной работе — хотя это важно. Главная загвоздка лежит в нерешённых вопросах теории кодирования, которые по-хорошему должны быть исследованы математиками ещё до того, как криптографы начинают строить свои схемы. Но криптографы всё это отложили и начали строить, надеясь, что теория подтянется. Она не подтянулась. Теперь мы застряли.»
# Code-based криптография: открытые проблемы в теории кодирования
**Code-based криптография** использует ошибки декодирования линейных кодов как основу для криптостойких схем. Её главный потенциальный плюс — устойчивость к будущим атакам с помощью квантовых компьютеров, в отличие от популярных сейчас систем, основанных на целочисленной факторизации или дискретном логарифме. Однако после почти двух десятилетий активного исследований она всё ещё остаётся в статусе «запасного варианта». И причина не только в технических ограничениях (большие ключи, низкая скорость), но прежде всего в фундаментальных пробелах в математической базе — теории кодирования. Эти пробелы прямо влияют на криптографическую безопасность и практическую реализуемость.
Что делает code-based криптографию «квантовостойкой»?
Чтобы понять, почему криптография на основе кодов рассматривается как будущее после квантовых компьютеров, нужно разобраться с её основой — задачами декодирования. Обычные криптосистемы, такие как RSA или ECC, строятся на математических проблемах, которые считаются сложными для классических компьютеров, но становятся решаемыми при наличии квантового устройства. Алгоритм Шора может эффективно факторизовать большие числа и вычислять дискретные логарифмы, подрывая безопасность этих систем.
Криптография на основе кодов опирается на другую проблему: «проблему декодирования с заданным весом ошибки». У вас есть линейный код — набор векторов, образующих пространство. К этому вектору добавляется определённое количество ошибок (случайный вектор с заданным небольшим весом — числом ненулевых позиций). Задача: найти исходное кодовое слово, зная только результат с ошибками и структуру кода (публичный ключ). Для линейных кодов с большими параметрами эта задача считается сложной даже для квантовых компьютеров, так как известные квантовые алгоритмы не дают существенного преимущества для её решения.
McEliece и Niederreiter: две основные схемы
Практически все криптографические схемы на основе кодов — это вариации двух классических конструкций: McEliece (1978) и Niederreiter (1986). Они используют одну и ту же математическую проблему, но в разных «обёртках».
Схема McEliece — это криптосистема с открытым ключом для шифрования. Публичный ключ представляет собой «замаскированную» матрицу генератора кода G’. Чтобы зашифровать сообщение, его кодируют с помощью G’ и затем добавляют случайный вектор ошибок e с фиксированным небольшим весом t. Только обладатель секретного ключа (знающий исходную структуру кода и способ преобразования G’ в G) может эффективно удалить эти ошибки и декодировать сообщение.
Схема Niederreiter — это схема цифровой подписи. Здесь публичный ключ — это «замаскированная» проверочная матрица кода H’. Подпись создаётся путём решения уравнения: найти вектор ошибок e (с весом t), такой что H’ * e = s, где s — хэш сообщения. Найти такой вектор без знания секретной структуры кода сложно.
Различия между схемами влияют на размер ключей и скорость операций, но их криптостойкость основана на одной проблеме декодирования.
Проблема не в криптографии, а в теории кодирования
Когда криптографы выбирают линейный код для своей схемы, они фактически выбирают две вещи: тип кода (например, код Гоппы, Reed-Muller, BCH) и его параметры (длина n, размерность k, минимальное расстояние d). Параметры определяют криптостойкость: вес ошибок t должен быть меньше d/2, чтобы декодирование было уникальным и сложным. Но безопасность всей схемы напрямую зависит от того, как хорошо мы понимаем свойства этого конкретного кода. И вот здесь начинаются проблемы.
Теория кодирования — хорошо развитая математическая дисциплина, но её результаты часто ориентированы на оптимизацию для задач передачи данных: максимизация скорости при заданной исправляющей способности. Криптографии нужны противоположные свойства: коды должны быть «плохими» для декодирования без секретного знания, но «хорошими» для исправления ошибок при наличии секрета. Баланс этих требований плохо изучен.
1. Недостаток кодов с «скрытой» структурой
Чтобы схема была безопасной, публичный ключ (замаскированная матрица) должен выглядеть как случайная матрица линейного кода. Если атакующий сможет определить исходный тип кода из публичного ключа, он может использовать специфические алгоритмы декодирования для этого типа кода и взломать схему. Поэтому криптографам нужны коды, которые после случайного преобразования (умножения на случайную матрицу, перестановки столбцов) становятся «неузнаваемыми».
На практике используется ограниченный набор кандидатов: коды Гоппы остаются наиболее популярными, поскольку их структура относительно хорошо скрывается при преобразованиях. Но даже для них нет формальных доказательств, что замаскированная матрица действительно неотличима от случайной. Для других типов кодов (Reed-Muller, BCH) эта проблема ещё серьёзнее. Теория кодирования не даёт достаточных инструментов для анализа «степени скрытия» структуры кода после таких преобразований.
2. Проблема точной оценки сложности декодирования
Криптографическая безопасность определяется сложностью решения задачи декодирования с весом t для конкретного кода. Нам нужны точные оценки: сколько операций потребуется лучшему известному алгоритму? Теория кодирования часто даёт верхние и нижние границы для минимального расстояния и декодирующей способности, но эти границы слишком широки для криптографических нужд.
Существуют эффективные алгоритмы декодирования для многих классов кодов (например, алгоритм Паттерсона для кодов Гоппы). Но их сложность оценивается эмпирически или на основе экспериментов. Формальная математическая модель, связывающая параметры кода (n, k, d) с временной сложностью алгоритмов декодирования для веса t, близкого к d/2, отсутствует. Криптографы выбирают параметры исходя из «лучших известных атак», но это не математическая гарантия.
3. Дефицит кодов с оптимальными криптографическими параметрами
Криптография нуждается в кодах, где вес ошибок t можно выбрать достаточно большим для безопасности, но достаточно маленьким для корректного декодирования с секретным ключом. Это означает, что нужно много кодов с различными комбинациями (n, k, d), причём d должно быть достаточно велико. Теория кодирования сосредоточена на поиске кодов с максимально возможным d для заданных n и k (проблема оптимизации минимального расстояния). Однако криптографии часто нужны коды с «неоптимальным» d — если d слишком велико, декодирование с секретным ключом может стать слишком простым, уменьшая разрыв между легальным декодированием и атакой.
По сути, криптографам нужна не просто таблица лучших кодов, а целое семейство кодов с плавно изменяющимися параметрами, где можно точно регулировать соотношение безопасности и эффективности. Такие семейства плохо исследованы.
А что с размерами ключей и скоростью?
Даже если математические проблемы были решены, code-based криптография столкнулась с практическими препятствими. Публичный ключ в схеме McEliece — это матрица размером k × n. Для достижения достаточной безопасности параметры должны быть большими (например, n=6960, k=5413 для одного из популярных предложений). Это приводит к ключам размером в мегабайты, что неприемлемо для многих приложений по сравнению с ключами RSA или ECC (килобайты).
Скорость операций также ниже: шифрование и дешифрование требуют операций с большими матрицами и векторами. Однако эти проблемы считаются техническими и потенциально решаемыми с помощью оптимизации, использования более компактных представлений кодов (например, циклических или квазициклических структур) и аппаратного加速. Фундаментальным барьером остаются именно теоретические пробелы.
Открытые направления для исследований
Чтобы code-based криптография перешла из категории «потенциальной» в «практическую», необходимо продвижение в нескольких специфических областях теории кодирования, которые пока остаются в тени.
- Разработка метрик «криптографической сложности» для кодов. Нужны не только классические параметры (n, k, d), но и формальные меры, оценивающие, как сложность декодирования меняется при увеличении веса ошибок t от 0 до d/2. Эта криптографическая кривая сложности должна стать основой для выбора параметров.
- Исследование устойчивости структуры кодов к маскировке. Математический анализ того, какие преобразования (перестановки, умножения на матрицы) действительно разрушают специфические признаки класса кода. Ответ нужен не только для кодов Гоппы, но и для альтернативных кандидатов.
- Поиск и классификация семейств кодов с регулируемым балансом. Необходимо систематически исследовать и описывать семейства линейных кодов, где можно плавно изменять параметры, получая предсказуемое изменение криптографической стойкости и эффективности легального декодирования.
- Интеграция с другими «квантовостойкими» математическими проблемами. Гибридные схемы, сочетающие code-based криптографию с проблемами на основе многомерных сеток (lattice-based) или хэш-функций, могут смягчить зависимость от нерешённых проблем теории кодирования, распределив риски.
Что это значит для специалистов ИБ в России?
В контексте российских регуляторных требований (ФСТЭК, 152-ФЗ) переход на квантовостойкие криптографические алгоритмы — вопрос не отдалённого будущего, а ближайшего планирования. Уже сейчас необходимо оценивать перспективные технологии для защиты данных с длительным сроком жизни.
Code-based криптография остаётся одним из кандидатов, но её принятие в качестве стандарта будет зависеть от прогресса в фундаментальной математической базе. Специалистам важно понимать не только технические характеристики схем (размеры ключей, скорость), но и глубину нерешённых теоретических проблем. Это поможет избежать рисков внедрения технологий, основанных на непроверенных или неполных математических гарантиях.
Российские научные и инженерные коллективы могут сосредоточиться именно на этих открытых проблемах теории кодирования, так как это область, где можно добиться существенного прогресса, влияющего на практическую криптографию в целом.
Пока большинство усилий в code-based криптографии направлено на оптимизацию и стандартизацию уже известных схем (McEliece с кодами Гоппы). Но настоящий прорыв произойдёт, только если криптографы и математики совместно решат базовые вопросы о свойствах линейных кодов в криптографическом контексте. Без этого даже самые оптимизированные реализации останутся в статусе экспериментальных.