Кодовая криптография: задачи декодирования
24 января 2019 г. в рамках научного семинара «Коды, исправляющие ошибки, и пост-квантовая криптография» выступил д.т.н., профессор, научный руководитель, и.о. директора МИЭМ НИУ ВШЭ Евгений Крук, основной темой доклада которого являлось обсуждение криптосистем, построенных на основе решения задачи декодирования произвольного кода, исправляющего ошибки.
Евгений Крук является одним из ведущих российских ученых в области помехоустойчивого кодирования, компьютерной безопасности и кодовой криптографии, руководит в МИЭМ научной лабораторией Интернета вещей и киберфизических систем.
Доклад содержал краткое введение в кодовую криптографию и описание двух основных кодовых криптосистем — системы Мак-Элиса и системы Нидеррайтера. Данные системы, разработанные на основе теории алгебраического кодирования, сегодня являются уже классическими, а принципы их работы лежат в основе целого класса последующих разработок. Основой стойкости кодовой криптографии является задача декодирования линейных кодов (общая задача декодирования является NP-сложной).
Система Мак-Элиса — первая криптосистема с открытыми ключами, разработанная в 1978 году, использующая в процессе шифрования порождающую матрицу линейного кода.
Система Нидеррайтера — криптосистема с открытыми ключами, разработанная в 1986 году. В отличие от криптосистемы Мак-Элиса, в криптосистеме Нидеррайтера используется проверочная матрица кода.
Обе системы не получили широкого распространения в криптографических приложениях, но в то же время являются кандидатами для пост -квантовой криптографии, так как устойчивы к атаке с использованием квантового компьютера.
Основным препятствием для внедрения кодовых криптосистем является большой размер ключей. Поэтому, после рассмотрения базовых криптосистем, участники семинара обсудили их возможные модификации, позволяющие уменьшить ключ без потери криптостойкости.
В конце доклада была рассмотрена атака Зорге на одну из предложенных модификаций системы Мак-Элиса. В результате было показано, что данная модификация фактически не позволяет уменьшить ключ, поскольку задача вскрытия модифицированной системы может быть сведена к решению задачи вскрытия классической системы Мак-Элиса.
Как показало активное обсуждение темы семинара, данная проблематика интересна участникам и дает исследователям широкое поле для реализации своих идей и получения новых результатов.