Постквантовая криптография как новый стандарт

Появление достаточно мощного квантового компьютера сделает неактуальными традиционные средства криптографии, поэтому уже сейчас разрабатываются постквантовые алгоритмы инкапсуляции ключа и электронной подписи. Они основаны на принципиально других математических задачах, которые останутся вычислительно сложными даже для квантовых процессоров. Такие исследовательские работы всё активнее ведутся в последние годы — как в России, так и за рубежом.

В июне специалисты российской компании «Криптонит» предоставили Техническому комитету по стандартизации «Криптографическая защита информации» (ТК26) Росстандарта пакет документов по разработанной ими постквантовой электронной подписи (ЭП) «Шиповник» (подробнее о ней см. статью «От Штерна до «Шиповника»: как изменится ЭЦП в постквантовую эру»).

Стойкость этой схемы базируется на задаче декодирования случайного линейного кода, которая является вычислительно сложной. Иными словами, в основу схемы подписи легли коды, исправляющие ошибки. Они часто применяются в телекоммуникациях, а их свойства хорошо изучены.

В пакет документов вошло описание схемы, теоретическое обоснование её стойкости, обоснование выбора параметров, а также модельная реализация. Теперь в течение нескольких месяцев лучшие эксперты России по кодам будут заниматься верификацией и обсуждением переданных материалов. При успешном прохождении проверок схема «Шиповник» может стать первым постквантовым криптографическим стандартом в России. У нас есть все основания рассчитывать на это — ведь статья с её обоснованием уже принята в печать в журнале «Прикладная дискретная математика», который рецензируется Scopus и Web of Science. Выход статьи запланирован на сентябрь этого года.

На Западе аналогичные работы начались раньше и проводятся более масштабно. В начале июля 2022 г. американский национальный институт стандартов и технологий (NIST) завершил третий этап конкурса постквантовых схем инкапсуляции ключа и электронной подписи, стартовавший в 2016 году.

В первом раунде было представлено 69 алгоритмов. Из них до финала дошли только 3 схемы ЭП: две из них, CRYSTALS-Dilithium и Falcon, построены на основе целочисленных решёток, а третья — SPHINCS+, строится на основе хэш-функций. Схемы подписи на кодах, исправляющих ошибки, в финал не вошли.

Скорее всего, это связано с тем, что к моменту старта конкурса (2016 год) в научном сообществе не было четкого понимания, какой именно должна быть электронная подпись на кодах. Из-за этого в каждом из предложенных на конкурс вариантов были найдены критические ошибки, и соответствующие работы не смогли пройти даже во второй тур конкурса.

«При работе над нашей схемой подписи мы решили не ориентироваться на NIST, а пойти своим путём. С ним тоже не все так гладко — размер подписи измеряется в сотнях килобайт. Но зато нет вопросов к безопасности схемы — в ней мы уверены», — поясняет специалист-исследователь лаборатории криптографии компании «Криптонит» Виктория Высоцкая.

Схема «Шиповник» обладает рядом значительных преимуществ, выделяющих её на фоне других. Среди них – небольшой размер открытого ключа, что ускоряет обмен ключами и уменьшает трафик. По этому параметру «Шиповник» превосходит все подписи на решетках. Самое же главное — стойкость схемы была полностью обоснована, причём доказательство построено с опорой лишь на те математические задачи, которые уже являются доказано сложными.

Про электронные подписи, вышедшие в финал конкурса NIST, такого сказать нельзя. Так, строгое обоснование стойкости приведено только в схемах CRYSTALS-Dilithium и SPHINCS+. Однако даже они строятся на предположении о сложности ряда задач, сложность которых не доказана. Из всех финалистов алгоритм SPHINCS+ самый трудный в реализации, да и работает он медленнее. Однако этот алгоритм был оставлен как резервный вариант, поскольку он единственный построен на другом математическом базисе — на основе хэш-функций, а не решёток.

Помимо схем электронной подписи, в финал NIST прошла одна схема инкапсуляции ключа — CRYSTALS-Kyber. Она обеспечивает защищённый механизм инкапсуляции ключей на основе ассиметричного шифрования и преобразования Фуджисаки–Окамото. Среди её преимуществ члены жюри отметили сравнительно небольшие ключи шифрования, которыми легко обмениваться, а также высокую скорость работы. При этом её доказательство строится на основе предположений о сложности задач, которые не являются доказано сложными.

Аббревиатура CRYSTALS расшифровывается как «криптографический пакет для алгебраических решеток». Существующий консенсус среди математиков состоит в том, что, по мере увеличения размерности решёток, требуемое для решения этих задач время будет расти экспоненциально. Поэтому задачи на решётках считаются стойкими к атакам с использованием классического компьютера. Однако вопрос стойкости к квантовым атакам остается открытым.

Ещё четыре схемы инкапсуляции ключа были оставлены членами жюри на дальнейшее рассмотрение. Среди них одна схема построена на изогениях (SIKE), а три – на кодах, исправляющих ошибки (McEliece, BIKE и HQC).

В рамках работ ТК26 компания «Криптонит» разрабатывает отечественный аналог схемы инкапсуляции ключа на основе кодов, исправляющих ошибки. В схеме будут использованы самые перспективные решения, аналоги которых предложены в прошедших отбор схемах с конкурса NIST.

Руководители NIST рассчитывают представить черновой вариант постквантового криптографического стандарта к 2025 году. Российские специалисты готовы разработать его примерно в те же сроки, причём с более строгим обоснованием стойкости каждого алгоритма.

Как признается разработчик трёх из четырёх вышедших в финал алгоритмов Питер Швабе: «Некоторые люди сомневаются в работе NIST, опасаясь, что агентство может стандартизировать методы шифрования по указанию АНБ, оставив бэкдоры для американской разведывательной службы. Мы точно знаем, что это уже происходило в прошлом. Однако теперь в проверку предложенных на конкурс алгоритмов вовлечены не только специалисты NIST, но и всё глобальное криптографическое сообщество».

#шифрование #криптография #CRYSTALS-Dilithium #Falcon #SPHINCS+ #стандарт #NIST #защита #математика #lang_ru #lang-ru #encryption #cryptography #standard #protection #mathematics

Источник