Криптография на основе кодов, исправляющих ошибки
На английском языке: Code-based cryptography
Коротко
Семейство квантово-устойчивых криптографических алгоритмов, стойкость которых основывается на предположении о вычислительной сложности задачи декодирования случайного линейного кода. В частности, на этой задаче основан финалист конкурса NIST — алгоритм Classic McEliece и альтернативные финалисты BIKE и HQC.
Криптографические алгоритмы данного семейства отличаются относительно высокой эффективностью, но обладают ключами большой длины. Кроме того, они весьма консервативны в плане безопасности. Усилия криптоаналитиков с 1978 года не смогли значительно уменьшить количество операций, требуемых для взлома криптографических систем на основе кодов, исправляющих ошибки, при условии корректного выбора их параметров.
Семейство квантово-устойчивых криптографических алгоритмов, стойкость которых основывается на предположении о вычислительной сложности задачи декодирования случайного линейного кода. В частности, на этой задаче основан финалист конкурса NIST — алгоритм Classic McEliece и альтернативные финалисты BIKE и HQC.
Криптографические алгоритмы данного семейства отличаются относительно высокой эффективностью, но обладают ключами большой длины. Кроме того, они весьма консервативны в плане безопасности. Усилия криптоаналитиков с 1978 года не смогли значительно уменьшить количество операций, требуемых для взлома криптографических систем на основе кодов, исправляющих ошибки, при условии корректного выбора их параметров.
Подробно
Теория кодирования всегда имела тесную взаимосвязь с криптографией, поэтому неудивительно, что наиболее известная криптографическая система на основе кодов, исправляющих ошибки — система McEliece — появилась в 1978 году, став одной из первых систем с открытым ключом. Значительно уступая по эффективности системе RSA, она не получила такого же широкого распространения. Однако в последнее время, после активизации исследований в области квантовых вычислений и публикации алгоритма Шора, эффективно взламывающего систему RSA на квантовом компьютере, способность системы McEliece противостоять квантовым атакам вновь привлекла внимание исследователей.
Система McEliece и подобные ей (система Нидеррайтера) могут быть реализованы с помощью различных классов кодов. В этой области хорошо известны результаты, полученные отечественной алгебраической школой — так, известный российский исследователь В.М. Сидельников показал нестойкость системы McEliece для некоторых классов кодов. В то же время известно, что применение кодов Гоппы позволяет получить стойкий и эффективный вариант этой системы. При анализе любой атаки на систему McEliece обычно отмечают насколько она применима для кодов Гоппы. В частности, система McEliece на кодах Гоппы — самый широко изученный алгоритм из числа участников конкурса NIST. Это значит, что вряд ли появится новая атака, которая существенно снизит стойкость схемы, в отличие от других классов алгоритмов.
Основанные на теории кодирования криптографические системы, как правило, используют простые двоичные операции и могут быть легко реализованы на программном и аппаратном уровне. В то же время они требуют больших объемов памяти для хранения ключей, представленных как проверочные матрицы линейных кодов большой размерности.
Интересной и актуальной задачей является создание эффективной схемы подписи на основе задач теории кодирования.
Теория кодирования всегда имела тесную взаимосвязь с криптографией, поэтому неудивительно, что наиболее известная криптографическая система на основе кодов, исправляющих ошибки — система McEliece — появилась в 1978 году, став одной из первых систем с открытым ключом. Значительно уступая по эффективности системе RSA, она не получила такого же широкого распространения. Однако в последнее время, после активизации исследований в области квантовых вычислений и публикации алгоритма Шора, эффективно взламывающего систему RSA на квантовом компьютере, способность системы McEliece противостоять квантовым атакам вновь привлекла внимание исследователей.
Система McEliece и подобные ей (система Нидеррайтера) могут быть реализованы с помощью различных классов кодов. В этой области хорошо известны результаты, полученные отечественной алгебраической школой — так, известный российский исследователь В.М. Сидельников показал нестойкость системы McEliece для некоторых классов кодов. В то же время известно, что применение кодов Гоппы позволяет получить стойкий и эффективный вариант этой системы. При анализе любой атаки на систему McEliece обычно отмечают насколько она применима для кодов Гоппы. В частности, система McEliece на кодах Гоппы — самый широко изученный алгоритм из числа участников конкурса NIST. Это значит, что вряд ли появится новая атака, которая существенно снизит стойкость схемы, в отличие от других классов алгоритмов.
Основанные на теории кодирования криптографические системы, как правило, используют простые двоичные операции и могут быть легко реализованы на программном и аппаратном уровне. В то же время они требуют больших объемов памяти для хранения ключей, представленных как проверочные матрицы линейных кодов большой размерности.
Интересной и актуальной задачей является создание эффективной схемы подписи на основе задач теории кодирования.
Как уже сегодня начать применять криптографию на основе кодов, исправляющих ошибки?
Команда QApp уделяет большое внимание исследованию криптографических алгоритмов на основе кодов, исправляющих ошибки, один из которых — алгоритм инкапсуляции ключа Classic McEliece — финалист конкурса NIST.
Команда QApp уделяет большое внимание исследованию криптографических алгоритмов на основе кодов, исправляющих ошибки, один из которых — алгоритм инкапсуляции ключа Classic McEliece — финалист конкурса NIST.