Введение 3
Глава 1. Цифровые подписи 6
§ 1. Цифровые подписи. Определение и примеры 6
§ 2. Общая идея затемненной цифровой подписи 8
§ 3. Затемненная цифровая подпись Эль-Гамаля 13
Глава 2. Частично затемненные цифровые подписи 15
§ 1. Определение частично затемненной цифровой подписи 15
§ 2. Пример частично затемненной подписи Эль-Гамаля 17
Глава 3. Криптография на решетках 18
§ 1. Определение решеток 18
§ 2. Вычислительно сложные задачи на решетках 20
§ 3. LLL-алгоритм 23
§ 4. Основные идеи подписей на решетках 27
Глава 4. Кольца целых алгебраических чисел 29
§ 1. Определение 29
§ 2. Циклотомические поля 30
Глава 5. Основной результат 33
§ 1. Идея протокола подписи 33
§ 2. Автоморфизмы сохраняют расстояния 34
§ 3. Выбор инвариантной решетки 36
§ 4. Протокол транзакции снятия со счета 38
Заключение 40
Список литературы
В современной математической криптографии особое место занимает постквантовая криптография. так принято называть те разделы криптографии с открытым ключом, в которых криптостойкость протоколов основывается на вычислительно сложных задачах, не поддающихся эффективному решению с помощью квантового компьютера. Известно несколько типов таких задач, и одними из самых значимых являются сложные задачи на решетках. Это задача о нахождении кратчайшего вектора решетки и задача о нахождении вектора, ближайшего к данному вектору. На задаче о нахождении вектора, ближайшего к данному, основаны несколько известных протоколов цифровых подписей.
С другой стороны, имеются несколько важных разновидностей цифровых подписей. В частности, практически важными являются затемненные подписи (blind signatures, подписи вслепую), [4], [14], и их модификации — частично затемненные подписи (partially blind signatures). Области применения этих подписей — финансовая криптография (электронные деньги) и электронное голосование. Не каждую подпись можно переделать в затемненную, и не из каждой затемненной подписи можно сделать частично затемненную. Известно довольно мало затемненных подписей, основанных на решетках [20], и всего одна частично затемненная подпись, основанная на решетках [17].
Цель нашей работы — дать новую схему (протокол) частично затемненной подписи, основанной на решетках.
Опишем вкратце содержание работы. Она состоит из пяти глав. Большую часть занимает изложение сведений, необходимых для понимания основного результата (глава 5).
В главе 1 напоминаются основные определения и примеры цифровых подписей [11], [12], затемненных цифровых подписей [4], [14].
В главе 2 рассказывается о частично затемненных подписях. Используется материал бакалаврской выпускной работы [7] и статьи [8].
В главе 3 напоминаются основные определения и факты из теории решеток. Основные источники [3], [15].
Особенностью нашей работы является использование решеток специального вида — колец целых алгебраических чисел и идеалов в этих кольцах. При этом роль векторных пространств, в которых эти решетки располагаются, будут играть поля алгебраических чисел (как конечномерные векторные пространства над полем рациональных чисел Q). В главе 4 даются основные определения и некоторые факты о полях алгебраических чисел и идеалах в таких кольцах [2], [10], [1], [13]. Более конкретно, для наших целей выбраны поля деления круга (циклотомические поля). Это один из наиболее хорошо изученных классов полей целых алгебраических чисел [19], [21]. В частности, известно, что группы Галуа (группы автоморфизмов) таких полей являются циклотомическими и очень просто описываются.
В главе 5 излагается основной результат работы. Основные особенности нашей подписи таковы:
1) используются решетки колец и идеалов целых алгебраических чисел;
2) затемнение осуществляется с помощью применения случайно выбранного автоморфизма поля (элемент группы Галуа);
3) параметр (натуральное число), делающий подпись частично затемненной, вводится прямо в решетку, то есть в определение кольца целых алгебраических чисел;
4) криптостойкость подписи основана на сложности нахождения ближайшего вектора решетки в векторном пространстве над полем рациональных чисел.
Результаты данной работы опубликованы в [8], [5], [6], [9] и докладывались на Лобачевских чтениях в 2017 и 2018 годах, а также на Итоговой научно-образовательной конференции студентов в апреле 2019 года.
Основным результатом данной работы является новая схема частично затемненной цифровой подписи, которая имеет ряд отличий от уже известных подписей. В частности, используется математический аппарат из теории целых алгебраических чисел. Этот аппарат достаточно содержателен, и позволяет конструировать разнообразные подписи, удовлетворяющие описанным выше принципам. Данная схема может найти широкое применение в финансовой криптографии и электронном голосовании.
[1] Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел: Пер. с англ. — М.: Мир, 1987. — 416 с.
[2] Боревич З. И., Шафаревич И. Р. Теория чисел. — 3-е изд.доп — М.: Наука. Главная редакция физико-математической литературы. — 1985. — 504 с.
[3] Глухов М. М., Круглов И. А., Пичкур А. Б., Черемушкин А. В. Введение в теоретикочисловые методы криптографии. — СПб.: Изд-во «Лань», 2011. — 400 с.
[4] Епишкина А.В. Обзор и анализ криптографических схем, реализующих электронную подпись «вслепую». / А.В.Епишкина, М.Я.Шимкив // Безопасность информационных технологий — 2015. — № 3. — С.51-58.
[5] Зиятдинова А. И. О некоторых схемах частичных затемненных подписей, использующих сложность задачи о дискретном логарифме. // Труды Математического центра имени Н. И. Лобачевского // Материалы шестнадцатой молодежной научной школы-конференции. — 2017. — Т. 55. — С.55-58.
[6] Зиятдинова А. И. Об одной постквантовой частично затемненной подписи. // Труды Математического центра имени Н. И. Лобачевского // Материалы семнадцатой молодежной научной школы-конференции. — 2018. — Т. 56. — С.126-127.
[7] Зиятдинова А. И. Параметризация некоторых затемненных цифровых подписей, аналогичных подписи Эль-Гамаля. - Выпускная квалификационная работа (бакалаврская работа), Казань, 2017. — 32 с.
[8] Зиятдинова А. И., Петров О. Ю. О затемненных цифровых подписях с параметром. // Итоговая научно-образовательная конференция студентов
Казанского федерального университета 2017 года: сб. статей: в 6 т. - Казань: Изд-во Казан. ун-та — 2017. - Т. 1. — С. 248-250.
[9] Зиятдинова А. И., Тронин С. Н. Об одной частично затемненной цифровой подписи, основанной на решетках, возникающих в теории алгебраических чисел. // Ученые записки института социальных и гуманитарных знаний. // Материалы XI Международной научно-практической конференции "Электронная Казань 2019" (Информационные технологии в современном мире). — №1(17). — 2019. — С.215-220.
[10] Манин Ю. И., Панчишкин А. А. Введение в современную теорию чисел. — М.: МЦНМО, 2009. — 552 с.
[11] Смарт Н. Криптография.— М.: Техносфера, 2006.—528 с.
[12] Черемушкин А.В. Криптографические протоколы. Основные свойства и уязвимости. — М.: Изд. центр «Академия», 2009. — 272 с.
[13] Януш Г. Дж. Алгебраические числовые поля. Пер. с англ. — Новосибирск: Научная книга (ИДМИ), 2001. — (Университетская серия. Т. 6). — 248 с.
[14] Ященко В.В. Введение в криптографию / Под общ. ред. В.В.Ященко. — 4-е изд., доп. — М.: МЦНМО, 2012. — 348 с.
[15] Bremner M. R. Lattice Basis Reduction. An Introduction to the LLL Algorithm and Its Applications. — CRC Press, Taylor and Francis Group, 2012. — xvii+316 pp.
[16] Daniele Micciancio, Oded Regev. Lattice-based Cryptography // Post Quantum Cryptography. : Second International Workshop, PQCrypto 2008 Cincinnati, OH, USA, October 17-19, 2008 Proceedings- Springer, 2009. — P. 47-191
[17] Haibo Tian, Fangguo Zhang, Baodian Wei. A lattice-based partially blind signature // Security Comm. Networks. — 2016. — V. 9. — Issue 12. — P. 1820-1828.
[18] Hoffstein Jeffrey, Howgrave-Graham Nick, Pipher Jill, Silverman Joseph H., Whyte William. NTRUSign: digital signatures using the NTRU lattice // Topics in Cryptology - CT-RSA 2003: The Cryptographers’ Track at the RSA Conference 2003, San Francisco, CA, USA April 13-17, 2003, Proceedings - P. 122-140.
[19] Lang S. Cycotomic fields l and II (Combined Second Edition). — 1990. — 435 c.
[20] Markus Ruckert. Lattice-Based Blind Signatures // Advances in Cryptology - ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings. — Springer, 2010. — P. 413- 430.
[21] Washington, Lawrence C. Introduction to cyclotomic fields. — 1982. — 392 c.