29.10 // Предложены теоретические методы использования квантового случайного оракула

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

В 1986 году в своей основополагающей работе Goldreich, Goldwasser и Micali дали ответ на вопрос о том, как сконструировать функции, которые выглядят случайными для классического противника (не обладающего квантовым компьютером). В частности, они определили псевдослучайную функцию (PRF), как обладающую таким свойством, что не существует никакого классического алгоритма, имеющего доступ к оракулу PRF, который мог бы отличить её от истинно случайной функции. Они предложили вариант построения таких функций на основе псевдослучайных генераторов. Позднее были предложены конструкции PRF на основе псевдослучайных синтезаторов, также как и напрямую из т.н. сложных проблем. Псевдослучайные функции стали важным инструментом в криптографии: например, они используются в конструировании идентификационных протоколов, блочных шифров, кодов аутентификации сообщений.

В классическом случае при анализе функций ищут различитель между функцией и случайным оракулом — RO, идеализированной моделью, выдающей истинно случайные числа, но каждый раз одинаковые при одинаковых запросах на входе. Представим, что квантовые компьютеры изобретены. Тогда модель классического RO станет неадекватной и потребуется анализ базовых строительных блоков квантовостойких протоколов на основе квантового оракула. Именно такой подход недавно предложил Mark Zhandry из Стэнфордского Университета в своей работе, описывающей конструирование квантовых случайных функций. Спонсорами выступили Национальный Фонд Научных Исследований и Агентство перспективных оборонных разработок США.

При более точном рассмотрении вопроса следует учесть две возможности: противник может делать при помощи квантового компьютера классические запросы к PRF, пытаясь найти различитель между ней и оракулом, проводя при этом некие квантовые вычисления; но он может делать непосредственно и сами запросы к функции квантовым образом. Это более сильное допущение лежит в основе требований к квантовой безопасности. Квантовый запрос состоит из отправки квантовых суперпозиций входов функции и получения суперпозиции выходов. Функция, стойкая к таким атакам названа квантовой псевдослучайной функцией (QPRF).

Так, если псевдослучайная функция используется в качестве кода аутентификации сообщений (MAC), то в квантовом мире противник может подбирать суперпозиции сообщений, вынуждая использовать квантовостойкий MAC.

Создание квантовостойких PRF предоставляет подход для симуляции случайного оракула, работающего на квантовых запросах. Если в классической схеме RO может быть симулирован на лету при помощи идеальной хэш-функции или абстрактной алгоритмической модели (запрос — проверка предыдущего значения — выбор генерации случайного числа с записью или чтения ранее существующего значения — ответ), то в квантовом случайном оракуле вся функция должна быть сгенерирована заранее, ведь в ответ даже на единичный запрос квантовый оракул выдаёт множество ответов сразу. Однако, как показывает автор в предыдущей работе, если количество запросов априорно ограничено q, то достаточно независимых 2q-функций. Но при неизвестном числе запросов квантовый оракул должен быть симулирован при помощи QPRF.

Первый интересный теоретический результат, который удалось получить автору, состоит в том, что стойкие PRF могут быть очевидно нестойкими QPRF. Такие PRF могут иметь очень большой период, неизвестный противнику и необнаружимый классическими методами. Но при квантовом запросе такой период будет выявлен и таким образом противник сможет отличить PRF от идеальной QPRF.

Другим интересным результатом оказалось то, что многие PRF являются QPRF. К ним относятся классические конструкции удваивающих генераторов Goldreich, Goldwasser и Micali, псевдослучайные синтезаторы Наора и Рейнгольда, конструкции на проблемах обучении с ошибками Banerjee, Peikert и Rosen. Последняя конструкция, хотя и построена на использовании алгебраических свойств решёток, предназначена для создания симметричных алгоритмов с возможностью более быстрой работы.

Открытыми вопросами, которые нуждаются в дальнейшем исследовании в данной работе отмечены следующие:

• Являются ли квантовостойкими PRP — псевдослучайные перестановки (блочные шифры). Несмотря на известность способов преобразований PRF — PRP для доказуемо безопасного создания блочного шифра, доказательство стойкости в модели с квантовыми запросами остаётся неясным.

• Возможно ли создание квантовостойких MAC.

Источник: Cryptology ePrint Archive