АНАЛИЗ КРИПТОГРАФИЧЕСКИХ СВОЙСТВ КВАНТОВОГО ХЕШИРОВАНИЯ

ВВЕДЕНИЕ 3
1. ОПРЕДЕЛЕНИЯ И ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ .... И
1.1. Графы И
1.2. Группы и характеры 8
1.3. Квантовое хеширование 9
1.4. Квантовое хеширование с использованием экспандеров ... О
2. АНАЛИЗ СТОЙКОСТИ К КОЛЛИЗИЯМ 15
3. АНАЛИЗ СТОЙКОСТИ К ВОССТАНОВЛЕНИЮ ПРООБРАЗА 13
ЗАКЛЮЧЕНИЕ 26

Купить

Хеширование имеет важное прикладное значение. Оно, в частности, активно используется в криптографии: например, на основе этого примитива строится множество протоколов цифровой подписи, так как удобно подписывать не само сообщение, а его образ —хеш. В этом случае хеш- функция должна обладать некоторыми свойствами, такими как устойчивость к коллизиям и устойчивость к восстановлению прообраза. Более подробно о криптографических хеш-функциях можно узнать в [1].
В настоящее время очень активно развивается тема квантовых вычислений. Это происходит в силу нескольких причин. Во-первых, показано, что для некоторых классов задач квантовые алгоритмы имеют оценки, экспоненциально лучшие, чем у любых классических алгоритмов. Например, в статье [2] авторы приводят конструкцию квантового конечного автомата, мощность множества состояний которого экспоненциально меньше, чем у любого эквивалентного классического (даже вероятностного) конечного автомата. В его основе лежит классически-квантовая функция, которая отображает длинный классический вход в короткое квантовое состояние (эту функцию называют quantum fingerprinting). Во-вторых, так как квантовые вычисления основаны на постулатах квантовой механики, и в силу теоремы о запрете копирования состояния кубита [3], то появляется возможность построения коммуникационных сетей, в которых осуществить перехват информации невозможно: по крайней мере вторжение злоумышленника можно сразу же определить. Наиболее яркий пример — это протокол BB84 [0]. Более того, известны оценки, накладывающие ограничения на объем извлекаемой классической информации из ансамбля к кубит. Например, согласно теореме Холево, из системы, состоящей из к кубит, можно извлечь не более, чем O(k) классических бит [5].
Существует ли квантовый аналог классической хеш-функции? Оказывается, что да. В работе [6] авторы предложили технику квантовых отпечатков, это были классически-квантовые односторонние функции. Идея заключалась в представлении двоичных слов фиксированной длины в виде квантовых состояний. Эта конструкция основывалась на кодах исправ-
ляющие ошибки (в данном случае были использованы коды Джастесена (Justesen)) и оказалась очень полезной в теории коммуникационной сложности: с помощью нее были построены коммуникационные протоколы в модели SMP для предиката EQ, продемонстрировавшие экспоненциальный выигрыш протоколов с использованием квантовых отпечатков по сравнению с классическими при условии, что стороны не владеют коррелированными источниками случайности, таким образом улучшая оценку коммуникационной сложности функции EQ. В статье также приводятся алгоритм (именуемый SWAP-тестом) для того, чтобы различать квантовые отпечатки с высокой вероятностью и нижняя оценка на размер квантового отпечатка, если вероятность ошибки зафиксирована и строго меньше 1 — это A(log n), где n — длина двоичного слова.
Позднее в статье [Ш] было показано, что квантовые отпечатки можно рассматривать как криптографический примитив. В этой работе используется конструкция, основанная на квазилинейных кодах. Оказывается, что такая классически-квантовая функция обладает повышенными криптографическими свойствами, демонстрируя повышенную информационную стойкость. Подход, использованный авторами для доказательства повышенной криптоустойчивости, применяется в нашей работе.
В [8] приводится определение недвоичных квантовых хеш-функций. В статье [9] показана связь множеств с ^-отклонением и квантовых хеш- функций. В работе ЦП] приводятся схемы квантового хеширования с использованием графов-экспандеров и экстракторов.
Квантовая хеш-функция отображает классическое слово в квантовое состояние, математически — в гильбертово пространство. Чем меньше размерность этих пространств, тем лучше — злоумышленник не сможет извлечь много информации. С другой стороны, здесь возникают коллизии. В квантовом случае нет коллизий в классическом смысле понимания этого термина, так как квантовые хеш-функции по построению инъективны. Однако квантовые образы двух различных сообщений могут располагаться так близко, что не будет возможности достоверно (с достаточно высокой вероятностью) их различать.
При построении квантовой хеш-функции необходимы параметры, как правило, некоторое количество случайной информации или случайных данных. Говоря очень простым языком, входное слово «перемешивается» с этими данными. Квантовый параллелизм позволяет осуществлять это очень эффективно: «смешивание» осуществляется сразу в нескольких подпространствах, позволяя уменьшить размер получаемого хеша. Как уже ранее упоминалось, для построения квантовых хеш-функций могут быть использованы случайные подмножества Zm [11], случайные коды [6, И], случайные автоморфизмы (конечной группы ) и, экспандеры и экстракторы [10].
На сегодняшний день квантовая криптография развивается очень активно. Актуальной задачей является построение и анализ квантовых криптографических протоколов. Для их построения необходимы соответствующие примитивы как, например, квантовые хеш-функции, обладающие необходимыми криптографическими свойствами. В нашей работе рассматривается схема квантового хеширования с использованием экспандеров из [10], проводится её анализ на устойчивость к восстановлению прообраза.
Постановка задачи
В рамках данной работы необходимо провести анализ криптографических свойств схемы квантового хеширования на экспандерах из работы [10]. Во-первых, рассмотреть устойчивость схемы к квантовым коллизиям, т. е. показать, что модуль скалярного произведения двух хешей различных сообщений ограничена сверху малой величиной. Во-вторых, доказать повышенную устойчивость к восстановлению прообраза, т. е. получить более сильную оценку (чем существующие) количества бит, доступных при измерении квантового хеша.
Практическая значимость
Ранее уже было упомянуто, что в настоящее время квантовые вычисления являются одной из самых бурно развивающихся областей: с одной стороны физики пытаются создать полноценный квантовый компьютер, который позволял бы решать практически полезные задачи, с другой — математики разрабатывают квантовые алгоритмы. Особый интерес представляет квантовая криптография, предлагающая новые возможности, которые невозможны при использовании только средств классической криптографии. Отдельно следует выделить задачу построения квантовых криптографических протоколов. Практическая значимость работы состоит в возможности непосредственного использования её результатов при криптоанализе таких протоколов. Также результаты работы могут быть использованы как некоторая база, на которой можно построить новые криптографические примитивы.
Купить