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

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

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

L = {Zv₁ + Zv₂ + · · · + Zv_n},

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

_{v1,v2 · · · vn}

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

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

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

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

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

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

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

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

Чтобы проиллюстрировать важность этапа выборки с отклонением с точки зрения безопасности, рассмотрим следующую схему ЭЦП. Подписывающее лицо имеет (короткий) секретный ключ – пару чисел s₁, s₂ ∈ R и открытый ключ - пару (a, t), где a ∈ R выбирается случайным образом, а t = as₁ + s₂. Далее, подписывающее лицо случайным образом выбирает y₁, y₂ ∈ R и отправляет u = ay₁+ y₂ проверяющему, который возвращает c ∈ R. Затем подписывающий вычисляет z_i = y_i + s_ic (i =1,2) и пересылает обратно z₁, z₂ на проверку равенство az₁ + z₂ − tc = u и является ли ||z_i|| достаточно малым ^[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.