Особенности применения теории решеток в схемах электронной цифровой подписи

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Особенности применения теории решеток в схемах электронной цифровой подписи

Пискова Антонина Владиславовна

аспирант

Аннотация

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

Ключевые слова: электронно-цифровая подпись, RSA, пост-квантовая криптография, схема Bliss, криптография, Преобразование Фиат-Шамира, теория решеток, Абелева группа, Евклидово пространство, схема идентификации

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 = {Z v 1 + Z v 2 + · · · + Z vn },

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

v 1,v 2 · · · 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. Основным плюсом данной схемы стало значительное улучшение на этапе выборки с отклонением. Как следствие, эта схема связала между собой теоретическую и практическую криптографию на основе теории решеток.

Чтобы проиллюстрировать важность этапа выборки с отклонением с точки зрения безопасности, рассмотрим следующую схему ЭЦП. Подписывающее лицо имеет (короткий) секретный ключ - пару чисел s 1, s 2 ? R и открытый ключ - пару (a , t ), где a ? R выбирается случайным образом, а t = as 1 + s 2. Далее, подписывающее лицо случайным образом выбирает y 1, y 2 ? R и отправляет u = ay 1+ y 2 проверяющему, который возвращает c ? R . Затем подписывающий вычисляет zi = yi + sic (i =1,2) и пересылает обратно z 1, z 2 на проверку равенство az 1 + z 2 ? tc = uи является ли ||zi || достаточно малым [7].

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

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

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

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

Заключение

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

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

Библиография

Размещено на Allbest.ru