1. Введение
2. Постановка задачи 4
3. Описание предметной области 4
3.1 Квантовые хеш-функции 4
3.2 Множества с малым отклонением 7
3.2.1 -сети для чистых состояний 8
3.2.2 Схема квантового хеширования на основе множеств с малым отклонением 8
3.2.3 Методы построения квантовых хеш-функций для циклических групп на основе множеств с малым отклонением. 9
3.2.3.1 Множества с малым отклонением для неабелевых групп 9
3.2.3.2 Множества с малым отклонением из алгебро-геометрических кодов
3.4 Экспандеры и экстракторы 11
3.4.1 Экспандеры 11
3.4.2 Блуждания по экспандеру 12
3.4.3 Конструкция Маргулиса 13
3.4.4 Графы Кэли, являющиеся экспандерами 13
3.4.5 Экстракторы 14
3.4.6 Экстракторы как графы 16
3.4.7 Экстрактор фон Неймана 16
3.4.8 Сравнение экспандеров и экстракторов 17
3.5 Конструкции квантовых хеш-функций 17
3.5.1 Квантовые хеш-функции 17
3.5.2 Экспандеры для квантового хеширования 18
3.5.3 Экстракторы для квантового хеширования 19
4. Алгоритмы решения задачи 20
4.1 Известная ранее хеш-функция 20
4.1.1 Полный перебор 20
4.1.2 Случайные выборки 21
4.1.3 Генетический алгоритм 21
4.1.4 Конструктивный алгоритм 24
4.2 Хеш-функция на основе экстрактора фон Неймана 24
5. Результаты 25
5.1 Известная ранее хеш-функция 25
5.1.1 Полный перебор 25
5.1.2 Случайные выборки 26
5.1.3 Генетический алгоритм 27
5.1.4 Конструктивный алгоритм 29
5.2 Хеш-функция на основе экстрактора фон Неймана 32
5.2.1 Полный перебор 32
5.2.2 Случайные выборки 33
5.2.3 Генетический алгоритм 33
5.3 Сравнение двух хеш-функций 34
Заключение 34
Список литературы 35
Существует огромное число задач, с которыми квантовый компьютер должен намного лучше справляться. На сегодняшний день по различным каналам передается огромное количество информации. Большая часть этой информации конфиденциальна, а это значит, что встает вопрос о безопасности в передаче информации. Для того, чтобы предотвратить утечку информации используют различные алгоритмы шифрования. Это влечет за собой наличие некоторого ключа к зашифрованным данным. Современные методы защиты информации, например криптографический алгоритм RSA, строятся на вычислительной сложности таких задач, как разложение числа на простые множители (факторизации).
Алгоритм Шора факторизации числа успешно справляется с данной задачей. В своей работе Питер Шор показал, что, грубо говоря, для квантового компьютера задача факторизации того же класса сложности, что и простое умножение. А значит необходимы новые методы, основанные на квантовых вычислениях.
Чтобы использовать криптографические алгоритмы, необходимо предварительно подготовить информацию. Для этого используют хеш-функции, преобразующие по определённому алгоритму входной массив данных произвольной длины в выходную битовую строку фиксированной длины. Для использования в криптографии на них налагаются некоторые дополнительные требования: необратимость и устойчивость к коллизиям.
Квантовая криптография строится на принципах квантовой механики и квантовой теории информации, гарантирующих такую односторонность. Предложено несколько подходов к построению квантовых односторонних функций: “классически-классические”: аргументами и значениями являются классические последовательности, “классически-квантовые”: аргументы — классические последовательности, значения — квантовые состояния.
В данной работе была исследована квантовая хеш функция. Для этого были реализованы несколько алгоритмов оптимизации, в том числе конструктивный алгоритм. Эксперименты показали, что конструктивный алгоритм дает хорошие результаты только при больших значениях входных параметров. А для данной функции лучшее решение дает генетический алгоритм.
Также в ходе работы была построена новая квантовая хеш-функция на основе экстрактора фон Неймана. Результаты, полученные в ходе её исследования, показывают, что и в этом случае генетический алгоритм является лучшим выбором.
