В современном обществе вопросы, связанные с информационной безопасностью, являются наиболее приоритетными. Для обеспечения конфиденциальности и целостности информации наряду со множеством организационно-правовых мероприятий, аппаратных средств защиты, используются также и программные средства защиты информации. Важную роль при этом играет криптография. Неотъемлемой частью криптографии являются криптографические примитивы(cryptographic primitives) - это некоторые базовые понятия и конструкции, например, криптографические хеш- функции. Хеширование имеет очень важное прикладное значение. Например, хеш-функции, обладающие криптографическими свойствами, занимают видное место при проектировании различных криптографических протоколов. Однако, при подробном анализе структуры криптографических хеш-функций выясняется, что различные сообщения могут отображаться в одинаковые хеш- значения, т.е. приходится сталкиваться с коллизиями. Хотя вероятность такого события и мала, и специально подобрать пару сообщений, образующих коллизию «сложно», в некоторых случаях это возможно.
Совсем иначе обстоят дела, если вместо классических хеш-функций рассматривать квантовые хеш-функции. В последнее время очень активно развивается тема квантовых вычислений. Квантовые вычисления основаны на постулатах квантовой механики. Здесь в качестве носителей информации выступают квантовые биты - кубиты. Стойкость таких квантовых хеш- функций обеспечивается фундаментальными постулатами квантовой механики, а также теоремой, которая утверждает, что скопировать состояние кубита невозможно. Построение таких функций подразумевает физическую односторонность. Эти функции не обладают коллизиями в классическом понимании. Поэтому они могут быть использованы в самых различных криптографических задачах.
В данной работе будут рассмотрены различные конструкции таких квантовых хеш-функций и их криптографические свойства [3, 22].
В первой главе приводится описание математического аппарата квантовых вычислений. Здесь рассматриваются математическое представление кубита, понятие пространства состояний, операций над кубитами и т.д.
Во второй главе рассматриваются различные квантовые гейты и их свойства.
В третьей главе речь идет непосредственно о самом квантовом хешировании, а именно, что из себя представляет квантовая хеш-функция, какими свойствами она должна обладать, чтобы ее можно было бы использовать в качестве криптографического примитива, рассматриваются квантовые аналоги коллизий. Также здесь рассмотрены методы построения квантовых хеш-функций на основе таких объектов из теории графов, как экспандеры и экстракторы.
В четвертой главе излагается материал, связанный с непосредственной практической реализацией библиотеки квантового хеширования.
Практическая значимость выпускной квалификационной (дипломной) работы состоит в возможности непосредственного использования результатов работы в реализации квантовых криптографических протоколов.
В данной работе было рассмотрено квантовое хеширование с помощью экспандеров и экстракторов, а также реализована библиотека квантового хеширования на языке Quipper.
После проведения вычислительных экспериментов мы убедились в том, что квантовое хеширование с помощью экспандеров является очень неэффективным при выбранных параметрах и методе реализации в том плане, что получаемые квантовые схемы очень больших размеров, соответственно, они очень долго генерируются и исполняются. Кроме того, для малых значений п получаемые квантовые хеш-функции не обладают необходимыми криптографическими свойствами: в силу того, что мощность множества параметров (длина случайного блуждания) достаточно велика, получаем «достаточно много» кубитов для формирования хеша, и вероятность извлечь информацию о хешированном слове велика. Но стоит заметить то, что такая конструкция является асимптотически оптимальной.
Если перейти к экстракторам, то здесь наблюдается полностью идентичная картина. Сложность квантового хеширования с использованием экстракторов обусловлена еще и тем, что теория экстракторов очень развита в теоретическом плане, а явные конструкции достаточно сложны в понимании и реализации.
Чтобы подобные конструкции можно было использовать в качестве эффективных криптографических примитивов, необходимы дальнейшие исследования.
