Квантовая передача информации: эффективные криптографические протоколы тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Зиятдинов Мансур Тагирович

• Зиятдинов Мансур Тагирович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Зиятдинов Мансур Тагирович

Введение

Глава 1. Предварительные сведения о квантовом хэшировании

1.1. Квантовые хэш-функции

1.2. Квантовые ветвящиеся программы и их вычисление

1.3. Бинарные и небинарные квантовые хэш-функции

Глава 2. Квантовое хэширование

2.1. Квантовое хэширование для абелевых групп

2.1.1. Структура квантовой хэш-функции для группы

2.1.2. Необходимое условие существования «хорошего» множества автоморфизмов

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

2.1.4. Подходы к реализации квантовых хэш-функций

2.2. Квантовое хэширование на основе графов

2.2.1. Дополнительные определения

2.2.2. Хэширование на основе экспандеров

2.2.3. Хэширование на основе экстракторов

2.2.4. Квантовые хэш-функции с ключом

Глава 3. Криптоанализ квантового хэширования

3.1. Энтропия квантового хэширования

3.1.1. Дополнительные определения

3.1.2. Протоколы

3.1.3. Энтропия Холево квантового хэша

3.1.4. Квантовая информационная стоимость квантовой хэш-функции

3.2. Выбор параметров квантовых хэш-функций

3.2.1. Выбор параметров методом отжига

3.2.2. Явные конструкции параметров

3.2.3. Сравнение различных методов

Заключение

Стр.

Список сокращений и условных обозначений

Список литературы

Список рисунков

Список таблиц

Приложение А. Исходный код программы вычисления параметров

квантового хэширования методом отжига

Приложение Б. Исходный код программы вычисления параметров

квантового хэширования перебором

Приложение В. Исходный код программы явной конструкции

параметров квантового хэширования

Приложение Г. Результаты поиска параметров

Г.1. Результаты поиска параметров

Г.2. Скрипты для обработки данных

Введение диссертации (часть автореферата) на тему «Квантовая передача информации: эффективные криптографические протоколы»

Квантовые вычислительные модели работают быстрее классических в целом классе задач [1]. Впервые это было отмечено независимо друг от друга Фейнманом [2] и Маниным [3] для задачи моделирования гамильтониана. Одним из наиболее известных квантовых алгоритмов с экспоненциальным превосходством над классическими стал алгоритм Шора [4] для разложения числа на простые множители. Этот же алгоритм стал первым приложением квантовых алгоритмов к криптографии. Следует отметить, что для многих подобных задач неизвестны нетривиальные оценки сложности классических алгоритмов (см., например, [5]), а появление полиномиальных верхних или нижних оценок будет означать либо равенство каких-либо классов сложности и «схлопывание» полиномиальной иерархии, либо неравенство этих классов и решение одной из проблем тысячелетия. Даже небольшие улучшения верхних или нижних оценок могут привести к довольно сильным результатам. Так, Уильямс показал [6], что из существования алгоритма, решающего задачу Circuit SAT от n переменных и nk гейтов за 2npoly(nk)/s(n), где s(n) — суперполиномиальная функция, следует неравенство NEXP С P/poly, т.е. суперполиномиальные нижние оценки сложности схем для задач, решаемых за недетерминированное экспоненциальное время.

Одним из наиболее сильных результатов о сравнительной сложности классических и квантовых алгоритмов является серия работ Ааронсона [7], Ааронсона и Амбайниса [8] и Раза и Таля [9], в которых показано, что существует оракул A, для которого релятивизированный класс BQP^ не содержится в релятивизи-рованной полиномиальной иерархии PHA.

В настоящее время наблюдается быстрый рост количества квантовых компьютеров, в том числе доступных по сети, также растёт и число кубит в них (до 20-50 кубит у разных производителей: например, IBM[10], Google[11], Microsoft[12]). В связи с этим появилось понятие NISQ-вычислений [13] (Noisy Intermediate-Scale Quantum — шумные квантовые вычисления промежуточного масштаба). В этой области исследуются вычисления, подверженные шумам, при количестве кубит от 50 до 100, например, довольно естественные задачи квантового машинного обучения, задачи квантовой криптографии. Область NISQ-вычислений, с одной стороны, доступна или станет доступна в ближайшее

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

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

Квантовая и постквантовая криптография. Практически с момента появления идей квантовых компьютеров одним из возможных их применений указывалась квантовая криптография — способ защиты данных, при котором «безопасность гарантируется законами физики» [14]. Это же применение на данный момент является наиболее развитым с практической точки зрения [15]. Другое последствие появления квантовых вычислений — исследования устойчивости криптографических средств к атакам, выполняемым при помощи квантовых компьютеров, т.н. «постквантовая криптография» [16].

Квантовое хэширование. Квантовое хэширование появилось как развитие идей вероятностного метода отпечатков, восходящего к работам Р. Фрей-валдса [17; 18]. Использовать метод отпечатков для квантовых вычислений первыми предложили, по-видимому, А. Амбайнис и Р. Фрейвалдс [19]. В их работе описан квантовый конечный автомат, который распознаёт язык Lp = {аг : i делится на простое p} с использованием всего 0(logp) состояний (или О (log log p) кубит). В явном виде метод сформулировали Г. Бурман, Р. Клив, Дж. Ватроуз и Р. де Вольф [20]. В их квантовом методе отпечатков двоичное слово w отображается в квантовый отпечаток |^(w)) с использованием кода Джастесена (Justesen), исправляющего константную долю ошибок в переданном слове. Возможность применения квантового метода отпечатков для криптографических целей принадлежит Д. Гавинскому и Ц. Ито [21]. Они показали, что при измерении квантового отпечатка |^(w)) можно получить не более константного количества бит информации о входном слове w. Обобщение квантового хэширования на случай небинарных последовательностей было произведено в работах Ф.М. Аблаева и А.В. Васильева [22; 23]. В отличие от квантовой хэш-функции Бурмана и др. хэшировалось не двоичное слово w е {0,1}п, а q-ичное число w е {0,1,... ,q — 1}. Так же, как и в других способах квантового хэширования, образы различных сообщений v = w практически ортогональны: |(tf(v)|tf(w))| ^ £ для произвольного наперёд заданного £ е (0,1). При этом для хэширования используется 0(loglog q + log(1 /£)) кубит.

Хотя квантовые хэш-функции и возвращают квантовый регистр с хэш-значением, на их основе можно конструировать и классические хэш-функции, которые принимают и возвращают классические значения. Так, в работе Ф.М. Аблаева и М.Т. Зиятдинова [24] квантовые хэш-функции используются для построения универсального семейства недетерминированных хэш-функций с классическими входными и выходными данными. Для этого исходная входная последовательность многократно преобразуется в квантовый хэш и выполняются серия измерений для получения последовательности классических значений. Построенные семейства позволяют различать аргументы: существует процедура, которая для полученных из различных входных данных выходных последовательностей, выдаёт, что они различны, причём вероятность ошибки не превосходит 1/4.

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

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Разработать возможные варианты обобщения квантовых хэш-функций.

2. Исследовать криптографическую стойкость разработанных квантовых хэш-функций.

3. Построить на основе квантовых хэш-функций криптографические протоколы для передачи информации.

4. Оценить криптографическую стойкость построенных криптографических протоколов передачи информации.

Научная новизна: Все результаты диссертации являются новыми, получены автором самостоятельно.

1. Впервые построены квантовые хэш-функции для групп и квантовые хэш-функции на основе графов.

2. Впервые построены квантовые имитовставки (хэш-функции с ключом).

3. Выполнено оригинальное исследование криптостойкости некоторых квантовых хэш-функций и протоколов на их основе.

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

протоколах квантовой передачи информации, могут быть использованы в курсах лекций по квантовой информатике, в спецкурсах магистратуры в КФУ по направлению «Математические методы и программные технологии защиты информации», «Классические и квантовые методы обработки информации».

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

Основные положения, выносимые на защиту:

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

2. Построены квантовые хэш-функции на основе графов-экспандеров и экстракторов.

3. Построены квантовые имитовставки — квантовые хэш-функции с ключом.

4. Выполнен анализ криптостойкости протоколов, основанных на квантовых хэш-функциях, с использованием энтропии Холево.

Апробация работы. Основные результаты работы докладывались на: международных конференциях «Проблемы теоретической кибернетики» (Казань, 2014), «Дискретные модели в теории управляющих систем» (Москва, 2015), «International Conference on Quantum Technologies» (Москва, 2017), «Проблемы теоретической кибернетики» (Пенза, 2017), «Third International Conference for Young Quantum Information Scientists» (Эрланген, Германия, 2017), «International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)» (Кремс-на-Дунае, Австрия, 2018), «Дискретные модели в теории управляющих систем» (Красновидово, Москва, 2018), «Quantum Structures» (Казань, 2018); симпозиуме «Современные тенденции в криптографии (CTCrypt)» (Казань, 2015); семинарах в МГУ (2015), Латвийском университете (2017) и КФУ (2018).

Личный вклад. Все результаты, выносимые на защиту, получены автором лично. Статьи [25—27] выполнены автором самостоятельно. В совместной статье [28] автору принадлежат разделы о квантовых хэш-функциях, основанных на графах-экспандерах, экстракторах и квантовых кодах аутентификации.

Публикации. Основные результаты по теме диссертации изложены в 12 печатных изданиях, 4 из которых изданы в журналах, рекомендованных ВАК, 8 — в тезисах докладов.

Объем и структура работы. Диссертация состоит из введения, 3 глав, заключения и 4 приложений. Полный объём диссертации составляет 95 страниц, включая 13 рисунков и 4 таблицы. Список литературы содержит 59 наименований.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Зиятдинов Мансур Тагирович

Основные результаты работы заключаются в следующем.

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

2. Построены квантовые хэш-функции на основе графов-экспандеров и экстракторов.

3. Построены квантовые имитовставки — квантовые хэш-функции с ключом.

4. Выполнен анализ криптостойкости протоколов, основанных на квантовых хэш-функциях, с использованием энтропии Холево.

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

- изучение других объектов, отличных от конечных групп и рассмотренных классов графов, на основе которых может быть построена квантовая хэш-функция и получение необходимых и достаточных критериев для такого построения;

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

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

В заключение автор выражает благодарность и большую признательность научному руководителю Аблаеву Ф. М. за поддержку, помощь, обсуждение результатов и научное руководство. Также автор признателен Васильеву А. В., Хадиеву К. Р. и Хадиевой А. И. за обсуждение отдельных разделов диссертации. Автор особо признателен жене Зиятдиновой Зульфие за внимание и постоянную поддержку.

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

Список литературы

1. Quantum Algorithm Zoo [Текст] / под ред. S. Jordan. — 2011-2018. — URL: https://quantumalgorithmzoo.org/.

2. Feynman, R. P. Simulating physics with computers [Текст] / R. P. Feynman // International journal of theoretical physics. — 1982. — Т. 21, № 6/7. — С. 467—488.

3. Манин, Ю. И. Вычислимое и невычислимое [Текст] / Ю. И. Манин. — М.: Советское Радио, 1980. — (Кибернетика).

4. Shor, P. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer [Текст] / P. Shor // SIAM Journal on Computing. — 1997. — Т. 26, № 5. — С. 1484—1509. — arXiv: 9508027 [quant-ph].

5. Вороненко, А. А. Основы кибернетики : учебное пособие [Текст] / А. А. Во-роненко. — М.: ИНФРА-М, 2021. — 189 с.

6. Williams, R. Improving Exhaustive Search Implies Superpolynomial Lower Bounds [Текст] / R. Williams // SIAM Journal on Computing. — 2013. — Янв. — Т. 42, № 3. — С. 1218—1244.

7. Aaronson, S. BQP and the Polynomial Hierarchy [Текст] / S. Aaronson. — 2009. — 25 окт. — arXiv: 0910.4698v1 [quant-ph].

8. Aaronson, S. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing [Текст] / S. Aaronson, A. Ambainis. — 2014. — 21 нояб. — arXiv: 1411.5729v1 [quant-ph].

9. Raz, R. Oracle separation of BQP and PH [Текст]: Technical Report TR18-107 / R. Raz, A. Tal; Electronic Colloquium on Computational Complexity. — 2018.

10. Gambetta, J. M. Building logical qubits in a superconducting quantum computing system [Текст] / J. M. Gambetta, J. M. Chow, M. Steffen // npj Quantum Information. — 2017. — Т. 3, № 1. — С. 2.

11. Commercialize quantum technologies in five years [Текст] / M. Mohseni [и др.] // Nature News. — 2017. — Т. 543, № 7644. — С. 171.

12. Q#: Enabling scalable quantum computing and development with a high-level dsl [Текст] / K. Svore [и др.] // Proceedings of the Real World Domain Specific Languages Workshop 2018. — ACM. 2018. — С. 7.

13. Preskill, J. Quantum Computing in the NISQ era and beyond [Текст] / J. Preskill // Quantum. — 2018. — Авг. — Т. 2. — С. 79.

14. Shor, P. W. Simple proof of security of the BB84 quantum key distribution protocol [Текст] / P. W. Shor, J. Preskill // Physical review letters. — 2000. — Т. 85, № 2. —

C. 441.

15. Large scale quantum key distribution: challenges and solutions [Текст] / Q. Zhang [и др.] // Optics express. — 2018. — Т. 26, № 18. — С. 24260—24273.

16. Bernstein, D. J. Introduction to post-quantum cryptography [Текст] /

D. J. Bernstein // Post-quantum cryptography. — Springer, 2009. — С. 1—14.

17. Freivalds, R. Probabilistic Machines Can Use Less Running Time. [Текст] / R. Freivalds // IFIP congress. Т. 839. — 1977. — С. 842.

18. Freivalds, R. Fast probabilistic algorithms [Текст] / R. Freivalds // International Symposium on Mathematical Foundations of Computer Science. — Springer. 1979. — С. 57—69.

19. Ambainis, A. 1-way quantum finite automata: strengths, weaknesses and generalizations [Текст] / A. Ambainis, R. Freivalds // Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280). — IEEE. 1998. — С. 332—341.

20. Quantum fingerprinting [Текст] / H. Buhrman [и др.] // Physical review letters. — 2001. — Февр. — Т. 87, № 16. — С. 167902. — arXiv: 0102001 [quant-ph].

21. Gavinsky, D. Quantum fingerprints that keep secrets [Текст] / D. Gavinsky, T. Ito // Quantum Information & Computation. — 2013. — Т. 13, № 7/8. — С. 583-606.

22. Ablayev, F. On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting [Текст] / F. Ablayev, A. Vasiliev // Electronic Colloquium on Computational Complexity. Т. 59. — 2008.

23. Ablayev, F. M. Cryptographic quantum hashing [Текст] / F. M. Ablayev, A. V. Vasiliev // Laser Physics Letters. — 2013. — Т. 11, № 2. — С. 025202.

24. Аблаев, Ф. М. Универсальное семейство хеш-функций на основе квантовых процедур [Текст] / Ф. М. Аблаев, М. Т. Зиятдинов // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. — 2020. — Т. 162, № 3. — С. 259—268.

25. Ziatdinov, M. Quantum Hashing. Group approach [Text] / M. Ziatdinov // Lobachevskii Journal of Mathematics. — 2016. — Vol. 37, no. 2. — P. 222—226. — arXiv: 1412.5135.

26. Ziatdinov, M. From graphs to keyed quantum hash functions [Text] / M. Ziatdinov // Lobachevskii Journal of Mathematics. — 2016. — Vol. 37, no. 6. — P. 705—712.

27. Ziatdinov, M. T. Attacking Quantum Hashing. Protocols and Their Cryptanaly-sis [Text] / M. T. Ziatdinov // Lobachevskii Journal of Mathematics. — 2018. — Vol. 39, no. 7. — P. 1039—1045.

28. Quantum Fingerprinting and Quantum Hashing. Computational and Cryptograph-ical Aspects [Text] / F. Ablayev [et al.] // Baltic J. Modern Computing. — 2016. — Vol. 4, no. 4. — P. 860—875.

29. Ablayev, F. On the concept of cryptographic quantum hashing [Текст] / F. Ablayev, M. Ablayev // Laser Physics Letters. — 2015. — Т. 12, № 12. — С. 125204. — arXiv: 1509.01268.

30. Ablayev, F. On computational power of quantum branching programs [Текст] / F. Ablayev, A. Gainutdinova, M. Karpinski // International Symposium on Fundamentals of Computation Theory. — Springer. 2001. — С. 59—70.

31. Nielsen, M. A. Quantum Computation and Quantum Information [Текст] / M. A. Nielsen, I. L. Chuang. — 2004. — С. 558—559. — arXiv: arXiv: 1011. 1669v3.

32. Stinson, D. R. On the connections between universal hashing, combinatorial designs and error-correcting codes [Текст] / D. R. Stinson // Congressus Numerantium. — 1996. — С. 7—28.

33. Зиятдинов, М. Т. О некоторых видах композиции квантовых хэш-генераторов [Текст] / М. Т. Зиятдинов // Проблемы теоретической кибернетики. Материалы XVII международной конференции. — 2014. — С. 104—106.

34. Зиятдинов, М. Т. Об одном способе квантового хэширования. Групповой подход [Текст] / М. Т. Зиятдинов // Проблемы теоретической кибернетики. Материалы XVII международной конференции. — 2014. — С. 106—109.

35. Wigderson, A. Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications [Текст] / A. Wigderson, D. Xiao. — 2008.

36. Nayak, A. V. Lower Bounds for Quantum Computation and Communication [Текст] : дис.... канд. / Nayak Ashwin V. — California, Berkeley, 1999. — arXiv: 1011.1669.

37. On the computational power of probabilistic and quantum branching program [Текст] / F. Ablayev [и др.] // Information and Computation. — 2005. — Т. 203, № 2. — С. 145—162.

38. Холл, М. Теория групп [Текст] / М. Холл. — М.: Издательство иностранной литературы, 1962.

39. Alon, N. The probabilistic method [Текст] / N. Alon, J. H. Spencer. — John Wiley & Sons, 2016.

40. Cramming More Power Into a Quantum Device [Текст] / под ред. J. Gambetta, S. Sheldon. — 2019. — URL: https://www.ibm.com/blogs/research/2019/03/ power- quantum- device/.

41. Quantum supremacy using a programmable superconducting processor [Текст] / F. Arute [и др.] // Nature. — 2019. — Т. 574, № 7779. — С. 505—510.

42. Стюарт, Р. Искусственный интеллект: современный подход, 2-е изд.: Пер. с англ [Текст] / Р. Стюарт, П. Норвиг // М.: Издательский дом Вильямс. — 2006.

43. Метод квантового хэширования [Текст] / Ф. М. Аблаев [и др.] // Проблемы теоретической кибернетики. Материалы XVIII международной конференции. — 2017. — С. 13—15.

44. Зиятдинов, М. Т. Об аутентификации сообщений при помощи квантовых имитовставок на основе графов [Текст] / М. Т. Зиятдинов // Проблемы теоретической кибернетики. Материалы XVIII международной конференции. — 2017. — С. 98—100.

45. Shaltiel, R. An introduction to randomness extractors [Текст] / R. Shaltiel // International Colloquium on Automata, Languages, and Programming. — Springer. 2011. — С. 21—41.

46. Gillman, D. A Chernoff bound for random walks on expander graphs [Текст] / D. Gillman // Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. — 1993. — С. 680—691.

47. Chen, S. Small-bias sets for nonabelian groups [Текст] / S. Chen, C. Moore, A. Russell // Approximation, randomization, and combinatorial optimization. algorithms and techniques. — Springer Berlin Heidelberg, 2013. — С. 436—451.

48. Vasiliev, A. Quantum Hashing for Finite Abelian Groups [Текст] / A. Vasiliev. — 2016. — arXiv: 1603.02209.

49. Ta-Shma, A. Short Seed Extractors Against Quantum Storage [Текст] / A. Ta-Shma // Proc. ACM STOC. — 2009. — С. 401-408. — arXiv: 0808.1994.

50. Hoory, S. Expander graphs and their applications [Текст] / S. Hoory, N. Linial, A. Wigderson // Bulletin of the American Mathematical Society. — 2006. — Т. 43, № 4. — С. 439—561.

51. Vershynin, R. High-Dimensional Probability [Текст] / R. Vershynin. — Cambridge University Press, 2018.

52. Guruswami, V. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes [Текст] / V. Guruswami, C. Umans, S. Vadhan // Journal of the ACM. — 2009. — Т. 56, № 4. — С. 1—34.

53. Ziatdinov, M. The Security of Quantum MAC [Text] / M. Ziatdinov // 3rd International Conference for Young Quantum Information Scientists. Book of Abstracts. — 2017. — P. 13.

54. Ziatdinov, M. Attacking Quantum Hashing. Protocols and their Cryptanalysis [Текст] / M. Ziatdinov // International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). Student Research Forum. — 2018. — С. 43—53.

55. Зиятдинов, М. Т. Квантовые хэш-функции для аутентификации сообщений [Текст] / М. Т. Зиятдинов // Дискретные модели в теории управляющих систем. Труды X Международной конференции. — 2018. — С. 136—139.

56. Alon, N. Random Cayley graphs and expanders [Текст] / N. Alon, Y. Roichman // Random Structures & Algorithms. — 1994. — Т. 5, № 2. — С. 271—284.

57. Васильев, А. В. Минимизация коллизий при квантовом хешировании [Текст] / А. В. Васильев, М. Т. Зиятдинов // Дискретные модели в теории управляющих систем. — 2015. — С. 52.

58. Лидл, Р. Конечные поля: В 2 т. Пер. с англ. [Текст] / Р. Лидл, Г. Нидеррайтер. — М.: Мир, 1988. — 430 с.

59. Touchette, D. Quantum Information Complexity [Текст] / D. Touchette // Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing - STOC '15. — 2015. — С. 317—326. — arXiv: 1404.3733.