Квантовое хеширование: основные свойства, эффективные конструкции тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Аблаев Марат Фаридович

• Аблаев Марат Фаридович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Аблаев Марат Фаридович

1.2 Квантовая система

1.3 Преобразования квантовых систем

1.4 Извлечение информации из квантовой системы

1.5 Классическое хеширование

1.5.1 Однонаправленная (one-way) функция

1.5.2 Функция, устойчивая к коллизиям

2 Квантовая хеш-функция

2.1 Квантовая функция

2.2 Квантовая однонаправленная функция

2.2.1 Проблема эффективной вычислимости квантовой функции

2.2.2 Проблема обратимости квантовой функции

2.2.3 Условие ^-обратимости квантовой функции

2.3 Устойчивость к коллизиям

2.4 Квантовая функция, е-устойчивая к коллизиям

2.5 Примеры квантовых функций

2.5.1 Квантовая Фурье-функция

2.6 Квантовая хеш-функция

2.6.1 Число кубит для функции, устойчивой к коллизиям: нижняя оценка

3 Конструкции квантовых хеш-функций

3.1 "Вещественно-амплитудные" конструкции

3.1.1 Двоичная конструкция

3.1.2 q-ичная конструкция

3.2 "Фазовые" конструкции

3.2.1 Двоичная конструкция

3.2.2 q-ичная конструкция

3.3 Генератор квантовой хеш-функции

3.3.1 Примеры генераторов квантовых хеш-функций

3.4 Конструкции на основе композиций

3.4.1 е-универсальное хеширование

3.4.2 Композиция семейств функций

3.4.3 Теорема о композиции

3.4.4 Теорема о композиции: следствия

3.5 Хеш-функции на основе линейных семейств функций

3.5.1 Хеш-функция на основе "техники отпечатков" Фрей-валда

3.5.2 Хеш-функция на основе универсального линейного семейства

3.6 Хеш-функции на основе кодов, исправляющих ошибки

3.6.1 Универсальные хеш-семейства и коды, исправляющие ошибки

3.6.2 Хеш-функции на основе линейных кодов

3.6.3 Хеш-функция на основе кода Рида-Соломона

4 Реализация квантовой хеш-функции. Протокол сравнения хешей

4.1 Вычисление квантовой функции

4.2 Квантовая ветвящаяся программа

4.3 Сложность реализации квантовой хеш-функции

4.4 Процедура REVERSE сравнения квантовых хешей

Заключение

Литература

Система обозначений

1) log a = log2 a.

2) | K | - мощность конечного множества K.

3) Zq = {0,... q — 1} — множество. Множество Zq с операцией сложения (по модулю q) (Zq, +) — абелева группа. Обозначение Zq будем в обоих смыслах (в смысле множество и группа).

4) Для простого q добавление операции умножение * со свойствами ассоциативности и закона дистрибутивности (Zq, +, *) превращает Zq в поле. В ряде случаев, чтобы подчеркнуть, что Zq рассматривается как поле будем наряду с Zq применять обозначение Fq.

5) Пусть X - конечное множество, K = |X|. В данной работе множество X, как правило, будет являться или множеством X = слов длины k в алфавите Е или множеством X = {0,1,..., q — 1} чисел.

6) Для комплексного числа z = тегф (z = x+iy) комплексно-сопряженное к нему z = z* = те—гф (z = z* = x — iy).

Норма комплексного числа |z |2 = zz* = zz.

7) Для комплексных векторов a = (ai,a2 ... ап), b = (b1?b2 ...bn) число (a, b) = ^n=i akbk скалярное произведение.

8) Для вектора a = (a1?... , ad) скалярное произведение порождает норму ||a||2 = \J(a,a).

9) Hd - d-мерное комплексно-значное векторное (Гильбертово) пространство с нормой ||.|| = ||.||2.

10) Через H2" обозначают 2s-мерное Гильбертово пространство — пространство состояний квантовой системы, образованное из s куби-тов.

(H2)®s другое обозначение пространства H2", используемое в нашей работе.

11) U* - матрица, комплексно-сопряженная к U.

12) UT - транспонированная матрица U.

13) U^ = (UT)* - эрмитово сопряжение к U.

14) |a) - вектор-столбец (кет-вектор) a.

15) (b| = (|b)T)* - вектор-строка (бра-вектор) b*.

16) (a | b) - скалярное произведение векторов |a) и |b).

17) |a) < |b) - тензорное (правое кронекерово) произведение векторов |a),|b).

Для |a) = (ai,..., a¿)T и |b) = (bi,..., b¡)T |a) < |b) = (aibi, aib2,..., aib¡, a2bi,..., a¿b¿)T.

18) |a)|b) = |ab) = |a) < |b)

19) |a)(b| = |a) < (b| — матрица размера d x l вида (a¿bj)d=i ■=i.

20) A<B - тензорное (правое кронекерово) произведение матриц A, B

í an • • • ain \ / bii • • • bik \

Для A = I . .. . 1 и B = I

\ ami • • • amn ) \bii • • • bik J

/ aiiB • • • ainB \

A <8> B = I

\ amiB • • • amnB )

21) A<d = A < A < • • • < A.

4-v-"

d

22) (A < B)(|ф) < |^)) = A|0) < B|^).

23) (|0i)<|^i), |02)<|^2^ = (ф | 02)(^i | ^2).

24) f (n) = O(g(n)) - существуют положительные константы c и n0, такие, что 0 < f (n) < cg(n) для всех n > n0.

25) f (n) = ^(g(n)) - существуют положительные константы c и n0, такие, что 0 < cg(n) < f (n)) для всех n > n0.

26) /(п) = 0($(п)), если /(п) = (п)) и /(п) = ОД(п)).

27) Функция /(ж) вычислима за полиномиальное время, если время вычисления ограничено п0(1), где п - размер входа;

28) Функция ](ж) вычислима за экспоненциальное время, если время

опо( 1)

вычисления ограничено 2 , где п - размер входа.

Введение диссертации (часть автореферата) на тему «Квантовое хеширование: основные свойства, эффективные конструкции»

Введение

Теория и практика квантовых вычислений и квантовая передача информации - это направления квантовой информатики активно развиваемые в последние десятилетия. Наиболее известным результатом в области квантовой криптографии на сегодняшний день являются протоколы квантовой выработки ключа (Quantum Key Distribution — QKD). См, например, книгу [25] и работу [14]. По сути сегодня под термином квантовая криптография понимается именно QKD исследования, во всяком случае эти исследования составляют львиную долю работ в области квантовой криптографии. QKD работы по сути начались в 1984 году с протокола BB84 (Bennett, Brassard) [13]. Эти исследования продолжают интенсивно развиваться в наши дни [25]. Это направление на сегодняшний день является больше направлением прикладной квантовой механики (квантовой инженерии), чем направлением квантовой алгоритмической криптографии. За прошедшие годы в мире достигнут значительный прогресс в построении различных QKD протоколов. Весомые результаты мирового уровня в области квантовой электроники и физике квантовой информации получены в России.

Серьезными достижениями алгоритмической квантовой криптографии и пожалуй наиболее известными результатами квантовой информатики являются квантовый алгоритм факторизации Питера Шора [27, 25].

Криптографическое сообщество в ответ на подобные потенциальные угрозы выработало и весьма интенсивно развивает направление постквантовая криптография [15]. Авторы [15] в 2009 году во введении своей работы эмоционально написали: "Imagine that it's fifteen years from now and someone announces the successful construction of a large quantum computer. The New York Times runs a frontpage article reporting

that all of the public-key algorithms used to protect the Internet have been broken. Users panic. What exactly will happen to cryptography?". С тех пор направление пост квантовая криптография разрабатывает криптографические системы, которые должны стать трудными для будущих квантовых компьютеров, предлагает ряд направлений противодействия квантовым компьютерам. Например, на основе хэш-функций.

В 2010-ые годы в исследовательской группе КФУ определено понятие квантовой хэш-функции, начаты исследования областей их применимости. Первые такие работы опубликованы в 2014 году: [5, 2, 3]. Квантовое хэширование и протоколы передачи информации на их основе квантово усиливают направление постквантовая криптография [15], предлагая квантовые методы защиты информации для борьбы с потенциальным квантовым взломщиком.

Диссертационная работа исследуют квантовые хэш-функции, ориентированные на криптографическое использование. Напомним, что хеш-функция f : En ^ Em — это сжимающая словарная функция, отображающая длинные слова (длины n) в алфавите Е в короткие (длины m, n > m). Криптография предъявляет ряд специальных требований на хэш-функции, которые обусловлены требованиями противостояния атакам на передаваемую и хранимую информацию. К таким требования относятся однонаправленность и коллизия устойчивость (подробно см. раздел 1.5).

Однонаправленность. Свойство однонаправленности означает, что значение v = f(w) должно легко вычисляться по аргументу w, но по значению v аргумент w восстановить должно быть сложно. Важно отметить, что все используемые на сегодняшний день однонаправленные функции — функции, для которых не известны быстрые алгоритмы их обращения — они являются "условно однонаправленными" ("условно односторонними") в следующем смысле: нет математических доказательств выполнения свойства однонаправленности ни для одной используемой криптографической хеш-функции. Сложность этой проблемы показывает следующий факт. Известно, что доказательство свойства однонаправленности для некоей хеш-функции f будет означать доказательство свойства P = NP (см., например, книгу [29]).

Коллизия устойчивость. Коллизией для сжимающей функции f

называют ситуацию, когда выполняется f (w) = f (v) для различных w и v. Понятно, что для сжимающих функций коллизии существуют. Коллизия устойчивость хеш-функции означает, что нахождение коллизий должно быть сложно.

Понятие квантовой хеш-функции является обобщением на квантовый случай понятия криптографическая хеш-функция. Квантовая хеш-функция отображает элементы конечных множеств в квантовые состояния. В диссертационной работе определяются и обсуждаются свойства однонаправленности и коллизия устойчивости квантовых хеш-функций. определяется понятие эффективной вычислимости квантовой функции на основе модели квантовой ветвящейся программы.

Первая глава. Первая глава диссертации представляет базовые понятия кубит, квантовый регистр и квантовое состояние регистра. Дается понятие преобразования регистра и квантового состояния. Дается понятие извлечения информации из квантового состояния.

Вторая глава. Во второй главе определяются квантовые функции (функции, отображающие элементы конечных множеств в квантовые состояния). Определяются квантовые аналогии свойств однонаправленности (one-way) и коллизия устойчивости. В этой главе определяется понятие эффективной вычислимости квантовой функции на основе модели квантовой ветвящейся программы. Определяются и обсуждаются свойства однонаправленности и коллизия устойчивости квантовой функции [35].

Важным результатом является Теорема 4, которая представляет нижнюю оценку на число требуемых кубит для выбранного е — показателя устойчивости к коллизиям. Такого типа оценка в различных контекстах появлялась в литературе, см., например, [17]. Мы приводим другое (геометрическое) доказательство нижней оценки на число требуемых кубит для выбранного е — показателя устойчивости к коллизиям.

Третья глава. Основные результаты, излагаемые в третьей главе, представлены в работах [3], [10]. Результат третей главы: Теорема 8 о композиции и следствия из нее является основным результатом диссертационной работы.

Утверждение Теоремы 8 о композиции предоставляет средство для

конструирования различных квантовых хеш-функций на основе композиции (классических) семейств универсальных хеш-функций и известных квантовых хеш-функций.

Описание конструкций квантовых хеш-функций (утверждение Теоремы 8) опирается на понятие генерации квантовой хеш-функции семейством (классических) функций (раздел 3.3). Содержательно: семейство ^ функций генерирует квантовое состояние

= (ао|0),...,ау_1^ - 1))т

(является генератором состояния )), если семейство ^ определяет (см. раздел 3.3) амплитуды {а : г € {0,... , й_ 1}}. Теорема о композиции 8 доказывает, что, если ^ является универсальным хеш-семейством (см. раздел 3.4.1), а семейство Н является генератором некоторой известной квантовой хеш функции (см. раздел 3.3), то их композиция О = ^ о Н (композиция семейств ^ и Н см. раздел 3.4.2) генерирует новую квантовую хеш-функцию.

Утверждения Теоремы 8 о композиции конкретизируются для двух форм квантовых хеш-функций — амплитудной (Теорема 9) и фазовой (Теорема 10). В качестве следствия из Теоремы о композиции 8 (а точнее в качестве следствий из Теорем 9 и 10) приводятся различные конструкции квантовых хеш-функций:

1) На основе универсального семейства функций применяемого в "технике отпечатков" Фрейвалда (Теорема 11 — для амплитудной формы хеш-функции и Теорема 12 — для фазовой формы хеш-функции).

2) На основе (известного) универсального линейного семейства функций (Теорема 13 — для амплитудной формы хеш-функции и Теорема 14 — для фазовой формы хеш-функции).

3) На основе линейных кодов, исправляющих ошибки (Теорема 15 — для амплитудной формы хеш-функции и Теорема 16 — для фазовой формы хеш-функции).

Эти конструкции квантовой хеш-функции конкретизируются для случая кода Рида-Соломона (Теорема 17 — для амплитудной формы хеш-функции и Теорема 18 — для фазовой формы хеш-функции).

Конструкции 1)-3) квантовых хеш-функций анализируются на оптимальность. Показывается, что конструкция 1) и 3) оптимальны по числу требуемых кубит и имеет достаточно хорошие характеристики однонаправленности и коллизия-устойчивости. Показывается, что конструкция 2) не оптимальна по числу кубит — экспоненциально далека от нижней оценки.

Четвертая глава. В четвертой главе представляется модель квантовой ветвящейся программы. Для примера квантовой хеш-функции демонстрируется ее вычисление в модели квантовой ветвящейся программы. Рассматривается процедура REVERSE сравнения квантовых хешей, кратко описывается возможный протокол идентификации на ее основе.

Глава 1

Предварительные сведения

В данной главе приводятся основные сведения, необходимые для представления материала диссертации. Даются понятие кубита и его формальные описания, понятие квантового регистра (системы кубитов) состояния квантового регистра, преобразование квантовых состояний, преобразования и извлечение информации из квантовых состояний.

В последнем разделе 1.5 главы дается определение классической криптографической хэш-функции и приводятся (кратко) требования на классические хэш-функции.

1.1 Кубит

Теория квантовых вычислений опирается на постулаты квантовой механики. Приведем необходимые сведения из книги [25].

Квантовый бит. Квантовый бит (кубит) является ключевым понятием теории квантовых вычислений. Кубит рассматривается как квантово-механическая система, состояние которой описывается комплексно-значными вектор-столбцам двумерного гильбертова пространства Н2 длины единица, т.е.

(1.1)

где вектор-столбцы

образуют ортонормированный базис в Н2, комплексные числа а и в удовлетворяют условию |а|2 + |в|2 = 1.

Приведенная формализация описывает многократно экспериментально подтверждённый факт, что кубит находится в суперпозиции своих базисных состояний |0) и |1) с амплитудами а и в соответственно. С точки зрения квантовой информатики это интерпретируется следующим образом: кубит может находится одновременно в состояниях | 0) и | 1) . Величины | а| 2 и | в| 2 задают вероятности обнаружения кубита в базисных состояниях |0) и |1) соответственно при измерении кубита.

Комментарий. Далее всюду в тексте под понятием "кубит" мы будем иметь ввиду "состояние кубита" как это и принято в литературе по квантовой информатике. Одновременно будем использовать и понятие "состояние кубита". Т.е. понятия "кубит" и "состояние кубита" являются синонимами в данной работе. Варианты применения в тексте этих терминов определяются некими не формализуемыми (литературными) ощущениями. Случай, когда мы будем иметь ввиду собственно квантовый регистр (т.е. квантово механическую систему), определяющий кубит, будет оговариваться особо.

Сфера Блоха. Сфера Блоха - это геометрическое представление состояния кубита в виде точки на единичной трехмерной сфере. Сфера Блоха является вариантом сферы Римана (один из способов геометрического представления комплексных чисел), применяемой в квантовой механике. Отметим, что в поляризационной оптике вариант используемой сферы Римана называют сферой Пуанкаре.

Сфера Блоха является обобщением представления комплексного числа г, для которого |2 = 1, в виде точки на единичной окружности. Действие однокубитных операторов удобно иллюстрируется на сфере Блоха и такое представление используется в квантовой механике. В

основе представления кубита в виде точки на сфере Блоха лежит следующее свойство.

Свойство 1. Для подходящих ф £ [0, 2п] и 9' £ [0, п/2] кубит (состояние кубита)

= а|0> + в |1> имеет следующее представление

> = cos ^|0> + вгф sin^|1>. (1.2)

Доказательство. Приведем для удобства чтения известные соображения, доказывающее это свойство. Амплитуды а и в кубита |^> представим в экспоненциальной форме

а = пв1ф1, в = Г2вгф2,

где 0 < фьф2 < 2п. Положим ф = ф2 — ф^ Тогда |^> записывается в виде

> = егф1 (ri|0> + бгфГ2|1>).

Далее. Модули r1 = |а| и r2 = |в| — положительные вещественными числа, а вектор |^> — единичный. Поэтому r2 + r| = 1. Т.е. для подходящего 9' £ [0,п/2] выполняется

r1 = cos r2 = sin

Теперь |^> приобретает вид

|^> = егф1 (cos^|0> + егф sin0/|1>) .

Множитель вгф1 игнорируют, т.к. |вгф112 = 1 (напомним, что для комплексного числа z имеем |z |2 = zz*, где z = eiY, а z* = e—), и он не влияет на результат измерения состояния кубита (не познаваемая характеристика кубита). Итак, состояние |^> можно задать в виде:

> = cos ^|0> + егф sin ^|1>.

□

Представление (1.2) кубита (Свойство 1) лежит в основе соответствующей геометрической интерпретации кубита. Действительно, пусть бгф sin 0 = x+iy и обозначим z = cos 0. Тогда x2+y2+z2 = 1, т.е. каждое состояние кубита соответствует точке на единичной сфере, задаваемой полярными координатами 0 и ф.

Заметим, что противоположная точка на сфере с координатами п—0 и п + ф соответствует состоянию

|ф') = cos(n — 0) |0> + вг(п+ф) sin(n — 0) 11>

= — cos 0|0)

_ Аф

sin 0|1)

(1.3)

Поэтому достаточно рассматривать только верхнюю полусферу (0 < 9' < п/2), т.к. состояния, соответствующие точкам нижней полусферы, отличаются только на множитель егп = -1, не имеющий наблюдаемого эффекта.

Вводя обозначение 9' = 29, получаем, что каждому состоянию

00 W = cos 210) + е'фsin 211),

(1.4)

где 0 < ф < 2п, 0 < 9 < п, соответствует точка на трехмерной единичной сфере, называемой сферой Блоха.

Рис. 1.1: Сфера Блоха.

Вещественные амплитуды. Описанное представление иллюстрирует состояние кубита в общем случае. Если ограничиться рассмотрением квантовых состояний с вещественными амплитудами, то условие

туд.

нормировки а2 + в2 = 1 есть уравнение единичной окружности, и, следовательно, кубит может быть представлен точкой на ней (рис. 1.2).

Таким образом, состояние кубита в вещественном случае вырождается в

|ф) = cos 0|0) +sin О|1) (1.5)

для некоторого О Е [0, 2п).

1.2 Квантовая система

Квантовая система (квантовый регистр). Под квантовой системой (квантовым регистром) будем понимать изолированную систему отдельных квантово механических систем, образующих кубиты. В частности, под квантовым n-регистром будем понимать изолированную систему, состоящую из n квантово механических систем, представляющих n кубит. Свойство изолированности важно - оно позволяет описывать систему преобразований (операций) над кубитами, составляющими систему, без учета влияний окружающей среды.

Состояние квантовой системы (квантового регистра). Согласно постулату квантовой механики с квантовым регистром можно связать состояние квантового регистра. Такое состояние полностью описывается единичным вектором из гильбертового пространства H. Такое про-

странство называют пространством состояний квантового регистра.

Обозначим через |i) вектор из 2п-мерного пространства H2", у которого на i-й позиции 1, а все остальные компоненты нулевые. Система векторов |0), |1), ..., |i), ..., |2n — 1) образует ортонормированный базис в пространстве H2". Будем также обозначать указанные векторы через 100 ... 0), 100 ... 1), ..., |bin(i — 1)), ..., 111... 1), где bin(i) - это двоичное представление числа i. Такая система векторов в квантовой информатике называется вычислительный базис. В дальнейшем будем рассматривать все преобразования квантовых n-регистров только в таком базисе.

Таким образом, состояние квантового n-регистра в общем случае

п /2"

описывается единичным вектором из пространства H2 :

2" —1 2" —1

№ = ai|i), где ^ Ы2 = 1.

¿=0 ¿=0

Такие линейные комбинации называют суперпозициями базисных состояний |i) с амплитудами

Разложимые и запутанные состояния. В случае, если n кубит находятся в состояниях |^i), |^2), ..., |^п), а состояние квантового n-регистра, состоящего из этих кубит, выражается через тензорное произведение их состояний:

= |^l) <g> ® ••• <8> |^n),

то такие состояния называются разложимыми.

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

Комментарий. Неразложимые состояния играют важную роль в построении квантовых алгоритмов. Они позволяют реализовывать контролируемые операции над состояниями регистров (см. следующий раздел для формальных описаний). Неформально контролируемая операция с точки зрения информатики - это условная операция. Например,

в случае, если у нас имеется квантовый 2-регистр, то операция CNOT (Control NOT) трактуется так: "если состояние первого кубита есть 1, то изменить состояние второго на противоположный, а если - 0, то оставить второй без изменения".

1.3 Преобразования квантовых систем

Динамика изменения. Постулат квантовой механики гласит, что динамика изменения состояния замкнутой квантовой системы описывается унитарными преобразованиями. Другими словами, состояние квантового регистра |^1> в момент времени ¿1 связано с состоянием |ф2) в момент времени ¿2 следующим образом:

|^1> = и ^2>,

где и - это унитарный оператор, зависящий только от и ¿2.

Реализация унитарных операторов базисным набором операций. Множество унитарных операторов континуально, но их можно сколь угодно точно представить в виде произведения унитарных операций из некоторого конечного универсального набора (базисного набора) [25].

Таковым набором является, например, совокупность следующих операторов:

11 11

; S =

1 0 0 i

; T = п

= e

e-in/8 0

0

CNOT =

1 0

0 0

0 1 0 0

0 0 0 1

0 0

1 0

Известно, что любое однокубитное унитарное преобразование можно с произвольной точностью е представить в виде произведения O(logc 1/е) операторов Н и п/8 (константа с приблизительно равна 2), а произвольное унитарное преобразование, действующее на в кубитах, может быть представлено в виде произведения 0(в24й) однокубитных и

e

CNOT операторов. Фазовый оператор $ включается в стандартный набор для реализации контролируемых операторов и для организации помехоустойчивых вычислений.

1.4 Извлечение информации из квантовой системы

Измерение. Информация о состоянии

2П —1

¿=0

квантового п-регистра получается в результате измерения этого регистра. Измерение регистра - это вероятностный процесс, т.е., измеряя регистр в состоянии |^>, мы получим любое из состояний |г> с вероятностью |а^|2.

Такое измерение носит название измерения в вычислительном базисе. Возможны измерения в других базисах, но в данной работе нам достаточно рассматривать измерения в вычислительном базисе

{|0>,..., |2П - 1>}.

1.5 Классическое хеширование

Приведем кратко основные положения классического криптографического хеширования. Под Хэш-функцией в математической кибернетике понимают сжимающую функцию: слова длины п отображаются в короткие слова длины т.

/ : ^ 2т, п > т.

Слова в алфавите 2 стандартно могут рассматриваться как запись натуральных чисел по основанию |Е|. Поэтому наряду с предыдущим обозначением будем писать

f : X ^ ¥,

где конечные множества X и ¥ это множества слов или множества чисел.

Криптография предъявляет ряд специальных требований на хэш-функции, которые обусловлены требованиями противостояния атакам на передаваемую и хранимую информацию.

1.5.1 Однонаправленная (one-way) функция

Материал данного раздела о свойстве однонаправленности излагается следуя [29].

Одним из центральных требований, является свойство однонаправленности (one-way property) функции. Формализация понятия однонаправленная функция следующая.

Рассмотрим функцию f : Е* — Е*. Определим следующий эксперимент Invert а,/ обращения функции f на основе полиномиального по времени алгоритма A и числа n Е N:

Определение 1.5.1 (Процедура обращения функции f.). Процедура обращения

Invert A,/ : N —^ {0,1}

• Выбирается произвольный элемент x Е Еп. Вычисляется значение y = f (x).

• Вероятностный (обращающий) алгоритм A для данных входов 1n и y выдает результат x'.

• Результат процедуры Invert^,/ полагается равным 1, если f (x') = y, и полагается равным 0, если f (x') = y.

На основе процедуры Invert формулируется понятие однонаправленной функции.

Определение 1.5.2 (Однонаправленная функция.). Функцию f : Е* — Е* называют однонаправленной, если выполняются следующие два условия:

• (Функция легко вычислима:) Существует полиномиальный (от длины аргумента) по времени алгоритм М/, вычисляющий f ; т.е., М/(x) = f (x) для всех x Е Е*.

• (Вероятность быстрого обращения функции незначительна:) Для произвольного полиномиального по времени вероятностного алгоритма A, обращающего функцию f, для произвольного полинома p(n) Е POLY выполняется

Pr[/nvertA,f(n) = 1] < 1/p(n).

Теорема 1. Существование однонаправленной функции влечет

P = NP.

Доказательство. Приведем простое доказательство этого известного факта. Предполагаем, что определения классов сложности P и NP известны. В предположении, что f — однонаправленная функция построим язык Lf из NP\P. Доказательство основывается на том, что если P = NP, то функция f не является однонаправленной.

1) Язык Lf определим условием

Lf = {w = (x,y, 1k) : существует u Е {0,1}k такое, что f (xu) = y}, здесь xu - это конкатенация слов x и u.

2) Язык Lf Е NP. Действительно. для слова v = (x,y, 1k) Е Lf слово u Е {0,1}k со свойством f (xu) = y является сертификатом доказательства вхождения слова v в Lf. Поскольку функция f быстро (полиномиально от длины ее аргумента) вычислима, то вычисление f(xu) с проверкой равенства f(xu) = y реализуются в полиномиальное время.

3) Покажем, что Lf Е NP\P. Для этого предположим, что P = NP. Т.е. имеем, что Lf Е P .В этом случае имеем следующий детерминированный алгоритм A, который обращает функцию f за полиномиальное время:

Input: (f(x), 1k)

z := 0; i := 1;

while i < k do

if (z0, f (x), 1k-i) Е L/ then z := z0 else z := z 1;

i := i + 1;

if f (z) = f (x) output z end-while

В алгоритме A в предположении, что P = NP имеем включение L/ Е P. Это включение обеспечивает быструю (детерминированную полиномиальную по времени) проверку условия (z0,f (x), 1k-i) Е L/. Другими словами быстро (детерминированно и полиномиально по времени) строится z такое, что f (z) = f (x). □

Комментарий. Таким образом все используемые на сегодняшний день однонаправленные функции — функции, для которых не известны быстрые алгоритмы их обращения — являются "условно однонаправленными".

1.5.2 Функция, устойчивая к коллизиям

Коллизией для сжимающей функции f называют ситуацию, когда выполняется f (w) = f (v) для различных w и v. Понятно, что для сжимающих функций коллизии существуют. Коллизия устойчивость функции (Стойкость функции к коллизиям) означает, что нет эффективного полиномиального алгоритма, позволяющего находить коллизии.

Криптографические хеш-функции. Прикладные требования. В криптографии (см., например, [26]) часто формулируют и уточняют требования однонаправленности и коллизия устойчивости в других терминах. Например, требования однонаправленности и коллизия устойчивости определяются в терминах сопротивление поиску первого прообраза, сопротивление поиску второго прообраза (слабое сопротивление поиску коллизий), стойкость к коллизии. Дополнительно формулируемое требование — требование лавинного эффекта (Avalanche effect): изменение одного символа аргумента должно вызывать изменение в среднем половины выходных символов (лавинное изменение) хеш-функции.

Глава 2

Квантовая хеш-функция

В данной главе определяются квантовые функции (функции, отображающие элементы конечных множеств в квантовые состояния). Определяются квантовые аналогии свойств однонаправленности (one-way) и коллизия устойчивости. В главе определяется понятие эффективной вычислимости квантовой функции на основе модели квантовой ветвящейся программы. Обсуждаются свойства однонаправленности.

Основным результатом главы является уточнение понятия е-коллизия устойчивости квантовой хеш-функции Определение 2.4.1 и Доказательство Теоремы 3 достаточного условия е-коллизия устойчивости квантовой хеш-функции

Другим важным результатом является Теоремы 4, в которой доказывается нижняя оценка на число требуемых кубит для выбранного е - показателя устойчивости к коллизиям. Такого типа оценка в различных контекстах появлялась в литературе, см., например, [17] . Мы приводим другое (геометрическое) доказательство нижней оценки и формулируем эту оценку в терминах коллизия устойчивости квантовой функции.

Материалы данной главы опираются на материалы работ [9, 11]. 2.1 Квантовая функция

Для конечного множества X и множества (H2)0s квантовых s кубит-ных состояний взаимно однозначную функцию

^ : X ^ (H2fs (2.1)

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

Примеры квантовых функций приводятся в разделе 2.5.

2.2 Квантовая однонаправленная функция

Понятие однонаправленная (one-way) или односторонняя функция должна удовлетворять двум условиям: а) "эффективная (быстрая) вычислимость" и б) "сложная обратимость". В соответствии с этими требованиями а) и б) мы определяем понятие квантовой однонаправленной функции.

2.2.1 Проблема эффективной вычислимости квантовой функции

Проблема реализации квантовой функции существенно зависит от выбора физической модели вычисления. Какая частица (какая субстанция) будет играть роль кубита. В случае организации квантового протокола передачи информации целесообразно ориентироваться на то, что роль кубит будут играть фотоны. В случае организации вычислений все зависит от выбираемой архитектуры вычислителя.

Мы ориентируемся на модель вычислений — квантовая ветвящаяся программа. Квантовая ветвящаяся программа, вычисления в ней и сложностные характеристики вычисления описывается в Главе 4.

2.2.2 Проблема обратимости квантовой функции.

Мы предлагаем формализацию понятия обратимости квантовой функции, основанное на понятии вероятности события правильного восстановления (правильного декодирования) аргумента и Е X квантовой функции

ф : X ^ (Н2)0 5

по ее значению |ф(и)). В работе [24] предлагается следующая формализация (излагается адаптированная версия в соответствии с применяемыми здесь обозначениями).

• Пусть дана функция V : (Н2)0в ^ X. Будем называть V — "декодированием квантовой й-кубитной системы" (кратко — "декодированием"). Содержательно декодирование V — это извлечение информации из квантового системы, состоящее из процесса измерения квантового состояния |ф) Е (Н2)0в и алгоритма преобразования результата измерения в элемент и множества X.

Список литературы диссертационного исследования кандидат наук Аблаев Марат Фаридович, 2022 год

Литература

[1] F. Ablayev, M. Ablayev, and A Vasiliev. Quantum hashing and fingerprinting for quantum cryptography and computations. In Henning Fernau, editor, Computer Science - Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 - July 3, 2020, Proceedings, volume 12159 of Lecture Notes in Computer Science, pages 1-15. Springer, 2020.

[2] F M Ablayev and A V Vasiliev. Cryptographic quantum hashing. Laser Physics Letters, 11(2):025202, 2014.

[3] Farid Ablayev and Marat Ablayev. Quantum hashing via e-universal hashing constructions and freivaldsfingerprinting schemas. In Helmut Jurgensen, Juhani Karhumaki, and Alexander Okhotin, editors, Descriptional Complexity of Formal Systems, volume 8614 of Lecture Notes in Computer Science, pages 42-52. Springer International Publishing, 2014.

[4] Farid Ablayev, Aida Gainutdinova, and Marek Karpinski. On computational power of quantum branching programs. In FCT, pages 59-70, 2001.

[5] Farid Ablayev and Alexander Vasiliev. Computing Boolean Functions via Quantum Hashing. In Cristian S Calude, Rusins Freivalds, and Iwama Kazuo, editors, Computing with New Resources, Lecture Notes in Computer Science, pages 149-160. Springer International Publishing, 2014.

[6] Farid M. Ablayev, Marat Ablayev, Joshua Zhexue Huang, Kamil Khadiev, Nailya Salikhova, and Dingming Wu. On quantum methods

for machine learning problems part I: quantum tools. Big Data Min. Anal., 3(1):41-55, 2020.

[7] Farid M. Ablayev, Marat Ablayev, Joshua Zhexue Huang, Kamil Khadiev, Nailya Salikhova, and Dingming Wu. On quantum methods for machine learning problems part II: quantum classification algorithms. Big Data Min. Anal., 3(1):56-67, 2020.

[8] Farid M. Ablayev, Marat Ablayev, Alexander Vasiliev, and Mansur Ziatdinov. Quantum fingerprinting and quantum hashing. computational and cryptographical aspects. Balt. J. Mod. Comput., 4(4), 2016.

[9] M. Ablayev. On quantum (£, e)-resistant hashing. Lobachevskii Journal of Mathematics, 37(6):758-767, Nov 2016.

[10] M. Ablayev and F. Ablayev. Quantum hashing via e-universal hashing constructions and classical fingerprinting. Lobachevskii Journal of Mathematics, 36(2):89-96, 2015.

[11] M. F. Ablayev. Efficient branching programs for quantum hash functions generated by small-biased sets. Lobachevskii Journal of Mathematics, 39(7):961-966, Sep 2018.

[12] A. Ben-Aroya and A. Ta-Shma. Constructing small-bias sets from algebraic-geometric codes. In Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on, pages 191-197, 2009.

[13] Charles H. Bennett and Gilles Brassard. Quantum public key distribution reinvented. SIGACT News, 18(4):51-53, 1987.

[14] Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. Theor. Comput. Sci., 560:711, 2014.

[15] Daniel J. Bernstein. Introduction to post-quantum cryptography, pages 1-14. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.

[16] Jurgen Bierbrauer, Thomas Johansson, Gregory Kabatianskii, and Ben Smeets. On families of hash functions via geometric codes and concatenation. In Douglas R. Stinson, editor, Advances in Cryptology - CRYPTO' 93, volume 773 of Lecture Notes in Computer Science, pages 331-342. Springer Berlin Heidelberg, 1994.

[17] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Phys. Rev. Lett., 87(16):167902, 2001.

[18] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.

[19] Ronald de Wolf. Quantum Computing and Communication Complexity. PhD thesis, University of Amsterdam, 2001.

[20] David Deutsch. Quantum computational networks. Royal Society of London Proceedings Series A, 425:73-90, 1989.

[21] Daniel Gottesman and Isaac Chuang. Quantum digital signatures. Technical Report arXiv:quant-ph/0105032, Cornell University Library, 2001.

[22] Alexander S. Holevo. Some estimates of the information transmitted by quantum communication channel (russian). Probl. Pered. Inform. [Probl. Inf. Transm.], 9(3):3-11, 1973.

[23] Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC '90, pages 213-223, New York, NY, USA, 1990. ACM.

[24] Ashwin Nayak. Optimal lower bounds for quantum automata and random access codes. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 369-376, 1999.

[25] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 1 edition, 2000.

[26] Bruce Schneier. Applied cryptography - protocols, algorithms, and source code in C, 2nd Edition. Wiley, 1996.

[27] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput, 26(5):1484-1509, 1997.

[28] D. R. Stinson. On the connections between universal hashing, combinatorial designs and error-correcting codes. In In Proc. Congressus Numerantium 114, pages 7-27, 1996.

[29] John M. Talbot and Dominic J. A. Welsh. Complexity and cryptography - an introduction. Cambridge University Press, 2006.

[30] Alexander Vasiliev. Quantum hashing for finite abelian groups. Lobachevskii Journal of Mathematics, 37(6):751-754, 2016.

[31] Ingo Wegener. Branching Programs and Binary Decision Diagrams. SIAM Monographs on Discrete Mathematics and Applications. SIAM Press, 2000.

[32] Mark M. Wilde. Quantum Information Theory. Cambridge University Press, 2 edition, 2017.

[33] Andrew Chi-Chih Yao. Quantum circuit complexity. In Proceedings of Thirty-fourth IEEE Symposium on Foundations of Computer Science, pages 352-361, Palo Alto, California, USA, 1993. IEEE Computer Society.

[34] А. Шень А. Ромащенко, А. Румянцев. Заметки по теории кодирования. Москва. Издательство МЦМНО, 2017.

[35] М. Аблаев. К вопросу о квантовой функции, устойчивой к коллизиям. Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 163(1):90-94, Ноябрь 2021.

[36] М. Аблаев Н. Салихова. Квантовый поиск заданной подстроки в тексте на основе техники хеширования. Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 162(3):241-258, декабрь 2020.