О новых задачах в асимметричной криптографии, основанной на помехоустойчивом кодировании

Рассматривается задача построения криптосистем с открытым ключом на основе помехоустойчивых кодов. Данный класс криптосистем на сегодняшний день является устойчивым к атакам с использованием квантового компьютера и потому может быть отнесен к методам постквантовой криптографии. Основным недостатком кодовой криптографии является очень большая длина открытого ключа. Большинство усилий по преодолению этого недостатка сводилось к замене кода Гоппы, который использовался в исходной криптосистеме, на код из другого множества, позволяющего описать открытый ключ более компактно, при этом сохранив стойкость криптосистемы к различным атакам. Здесь предложен другой подход к сокращению длины ключа – мы ставим задачу простого описания множества исправимых кодом ошибок, вес которых превосходит половину его минимального расстояния или которые не могут быть исправлены без знания некоторого скрытого преобразования. Если структура кода позволяет дать такое описание множества ошибок, то сложность большинства атак на зашифрованный текст (например, атака по информационным совокупностям) существенно возрастает.