Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

Features of applying lattice theory in digital signature schemes

Piskova Antonina Vladislavovna

graduate student, Department of Design and Security of Computer Systems, ITMO University

197101, Russia, Saint Petersburg, Kronverkskii prospekt, 49

piter-ton@mail.ru
Korobeinikov Anatolii Grigor'evich

Doctor of Technical Science

professor, Pushkov institute of terrestrial magnetism, ionosphere and radio wave propagation of the Russian Academy of Sciences St.-Petersburg Filial

199034, Russia, g. Saint Petersburg, ul. Mendeleevskaya, 1

Korobeynikov_A_G@mail.ru
Other publications by this author
 

 

DOI:

10.7256/2306-4196.2016.2.17970

Received:

12-02-2016


Published:

03-03-2016


Abstract: The subject of the study is the scheme of digital signature, which is an important element in building secure systems used in most real-world security protocols. Reliability of existing schemes of electronic digital signature can be severely lowered in case of developments in classical cryptanalyst or progress in the development of quantum computers. A potential alternative approach is to construct the schemes based on the complexity of certain properties of the lattices, which are supposed to be intractable for quantum computers. Due to significant scientific advances in recent years, scheme based on lattice theory already used in practice and is a very viable alternative to number-theoretic cryptography. The study is based on the use of methods of lattice theory. This choice is dictated by the lack of solution of problem of finding the shortest vector or finding the nearest vector in polynomial time. The main conclusion of the paper is that the main area of future development in the schemes of the digital signature on the basis of lattice theory is their optimization and implementation of the Fiat-Shamir model in it. For example, Bliss scheme showed high performance and therefore it can be integrated into portable systems and devices.


Keywords:

digital signature, RSA, post-quantum cryptography, Bliss scheme, cryptography, Fiat-Shamir transformation, lattice theory, Abelian group, Euclidean space, identification scheme


Введение

Согласно алгоритму Шора, с наступлением эры квантовых компьютеров, их огромная вычислительная мощность может вызвать сбой многих, используемых сегодня криптографических схем. В частности, станут уязвимыми схемы, основанные на задаче дискретного логарифмирования или теоретико-числовых сложных проблемах, к которым относятся почти все схемы шифрования с открытым ключом, включая эллептическую криптографию, схемы RSA и DSA [1,2]. Соответственно, это привело к появлению пост-квантовой криптографии, которая создает алгоритмы для противостояния квантовым технологиям. Криптография на основе теории решеток является наиболее надежной и перспективной среди многих важных пост-квантовых исследований. Ее главным преимуществом по сравнению с другими является то, что она обладает расширенной функциональностью и, в то же время, более эффективна для основных примитивов шифрования с открытым ключом и схем электронно-цифровой подписи (ЭЦП). Вычислительные проблемы, которые существуют в теории решеток, такие как нахождение кратчайшего вектора (Shortest Vector Problem) или нахождение ближайшего вектора (Closest Vector Problem) считаются устойчивыми к квантово-компьютерным атакам, что говорит о вычислительной нераскрываемости. С точки зрения безопасности и практичности, такие свойства перспективны для замены нынешних асимметричных схем, которые будут подвержены атакам в пост-квантовом мире.

Базовые положения исследования

В случае n – мерного Евклидова пространства, решетка – это дискретная абелева подгруппа максимального вектора, то есть подгруппа, имеющая вид:

L = {Zv1 + Zv2 + · · · + Zvn},

где Z - кольцо целых чисел,

v1,v2 · · · vn

Ранг решетки равен n, размерность - m. Решетку называют полноранговой, если n = m.

В зависимости от сложности решетки, схемы ЭЦП, как правило, делятся на три категории, а именно схемы GGH/NTRU, хэш-знаковые подписи и подписи Фиата - Шамира.

Одними из первых схем, основанных на сложности теории решеток, а именно, на трудности поиска кратчайшего вектора решётки, были криптосистемы GGH и NTRUEncrypt. Отличие между этими схемами заключается в том, что последняя может в некоторой степени рассматриваться как частный случай первой. В 2009 году эти схемы были взломаны, благодаря работам Нгуена и Реджева [3].

Схемы ЭЦП, основанные на хэш-знаковой подписи, легли в основу в работы Диффи и Хеллмана. Идея состояла в том, чтобы захешировать сообщение перед его подписанием. Эта теория стала основой для FDH хэша, где хэш-функция H (•) генерировалась случайным образом. Однако позже было показано, что такая схема существенно незащищена от атаки с выбором сообщений.

Подписи Фиата-Шамира

Существует альтернативный способ построения ЭЦП – сначала создать определенную схему идентификации, а затем преобразовать ее в ЭЦП посредством трансформации Фиата-Шамира. Идентификация проходит между двумя сторонами, где одна сторона (доказывающая) должна убедить другую сторону (проверяющую), что она является тем, за кого себя выдает. Данную реализацию можно наблюдать на примере часто используемого доказательства с нулевым разглашением - протокола Шнорра [4]. Главным образом благодаря исследованиям Любашевского с соавторами трансформация Фиата-Шамира используется в схемах ЭЦП (схема LYU) на основе теории решеток.

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

Безопасность схемы ЭЦП зависит от сложности поиска коллизий в отдельных семействах хэш-функций. Противник, умеющий подделывать подписи может использовать это в будущем, для нахождения коллизии в хэш-функции, выбранной случайным образом из семейства H [5]. Это означает, что если ЭЦП подвержена фальсификации, то существует алгоритм, который может решить задачу нахождения кратчайшего вектора для γ = O(n2) в поле R за полиномиальное время. Следовательно, подделывание подписи и кроме того нахождение коллизии в случайно выбранной h ← H эквивалентно задаче нахождения кратчайшего вектора решетки над R, то есть краткому целочисленному решению в кольце вычетов [6].

Настоящими прорывом в схемах ЭЦП на основе решеток стала схема, предложенная Дюкасом с соавторами и названная Bliss. Основным плюсом данной схемы стало значительное улучшение на этапе выборки с отклонением. Как следствие, эта схема связала между собой теоретическую и практическую криптографию на основе теории решеток.

Чтобы проиллюстрировать важность этапа выборки с отклонением с точки зрения безопасности, рассмотрим следующую схему ЭЦП. Подписывающее лицо имеет (короткий) секретный ключ – пару чисел s1, s2R и открытый ключ - пару (a, t), где aR выбирается случайным образом, а t = as1 + s2. Далее, подписывающее лицо случайным образом выбирает y1, y2R и отправляет u = ay1+ y2 проверяющему, который возвращает cR. Затем подписывающий вычисляет zi = yi + sic (i =1,2) и пересылает обратно z1, z2 на проверку равенство az1 + z2tc = u и является ли ||zi|| достаточно малым [7].

На графиках, представленных на Рис.1 и Рис.2 показано влияние гауссовского распределения на выборку с отклонением. На Рис. 1 показана схема LYU, а на Рис. 2 – схема Bliss.

._1

Рис. 1. Схема LUY.

.2

Рис.2. Схема Bliss

Распределение z отмечено голубым цветом, определяя и множество всех y в схеме на Рис. 1. В схеме на Рис. 2 представлены все (b,y) с отклонением шага и разложением на Декартово произведение. Черные кривые представляют масштабированный (1/М) алгоритм задачи распределения. Необходимо отметить, что вероятность совпадения на схеме Рис. 2 гораздо больше, чем на схеме Рис. 1.

Заключение

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

Базируясь на результатах исследований схем ЭЦП, проделанных в данной работе, можно сделать вывод, что основной областью будущих разработок в схемах ЭЦП на базе теории решеток будет являеться их оптимизация и внедрение в них модели Фиата-Шамира. В частности схема Bliss показала очень хорошую производительность и вполне может быть интегрирована в портативные системы и устройства. Интересным направлением будущих исследований может стать оценка практических последствий алгоритмов сжатия и оптимизации схемы Bliss.

References
1. Korobeinikov A.G., Vorob'ev A. O., Sidorkina I. G., Pylin V. V. Analiz kriptograficheskoi stoikosti algoritmov asimmetrichnogo shifrovaniya informatsii//Izv.VUZOV. Priborostroenie. 2007. T. 50. № 8., str. 28-32.
2. Korobeinikov A.G., Kutuzov I.M. Algoritm obfuskatsii// NB: Kibernetika i programmirovanie. — 2013.-№ 3.-S.1-8. DOI: 0.7256/2306-4196.2013.3.9356. URL: http://e-notabene.ru/kp/article_9356.html
3. Thomas Poppelmann and Tim Guneysu. Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware//LATINCRYPT. – 2012. – R. 139–158.
4. Ozgur Dagdelen, Marc Fischlin, Tommaso Gagliardoni. The Fiat-Shamir Transformation in a Quantum World // ASIACRYPT.-2013.-№2.-R. 62–81.
5. Vadim Lyubashevsky. Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures // ASIACRYPT.-2009. – R. 598–616.
6. Vadim Lyubashevsky. Lattice Signatures without Trapdoors // EUROCRYPT.-2012. – R. 738–755.
7. Leo Ducas and Daniele Micciancio. Improved Short Lattice Signatures in the Standard Model // CRYPTO.-2014. – R. 335–352