Криптография на решётках

Криптография на решётках — подход к построению алгоритмов асимметричного шифрования с использованием задач теории решёток, то есть задач оптимизации на дискретных аддитивных подгруппах, заданных на множестве ${ℝ}^n$.

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

Предпосылки создания

Шаблон:Чистить раздел В 1995 году Питер Шор продемонстрировал полиномиальный алгоритм для взлома криптографических систем с открытым ключом при использовании квантового компьютера, тем самым определив период существования данных систем до возникновения квантовых вычислителей достаточной размерности.

В 1996 году Лов Гровер продемонстрировал общий метод поиска в базе данных позволяющий производить расшифровку симметричных алгоритмов шифрования, эквивалентную двукратному уменьшению ключа шифра.

В 2001 году группа специалистов IBM продемонстрировала выполнение алгоритма факторизации Шора для числа 15. Число было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами, построенного из 18¹⁰ молекул, состоящих из пяти атомов фтора и двух атомов углерода, с записью информации посредством радиосигналов и считыванием методами ядерного магнитного резонанса.

Начиная со второй половины 1990-х годов возникла необходимость поиска криптостойких к квантовым компьютерам задач для постквантовой эпохи шифрования, в качестве одного из подходов было предложено использовать решётки в ${ℝ}^n$ — дискретные подгруппы вещественного векторного пространства, линейные оболочки которых совпадают с ним:

$L=\{\sum _{i=1}^n{\lambda }_i{b}_i\mid {\lambda }_i\in \mathbb{Z}\}$

Вычислительно сложные задачи

Синей точкой обозначен самый короткий вектор

Задача нахождения кратчайшего вектора (SVP, Шаблон:Lang-en) — найти в заданном базисе решётки ненулевой вектор по отношению к определённой нормали.

Задача нахождения (приблизительно) идеального кратчайшего вектора (ISVP, Шаблон:Lang-en) не считается NP-сложной. Однако, нет известных решёток, основанных на методе редукции, значительно более эффективных на идеальных структурах, чем на общих.

Ещё одна задача — нахождение (приблизительно) кратчайшего независимого вектора (SIVP, Шаблон:Lang-en), в которой дан базис решётки $B$ и требуется найти $n$ линейно независимых векторов.

Синяя точка — найденный вектор, красная точка — заданный вектор

Задача нахождения ближайшего вектора (CVP, Шаблон:Lang-en) — нахождение вектора в решётке по заданному базису и некоторому вектору, не принадлежащему решётке, при этом максимально схожего по длине с заданным вектором.

LLL-алгоритм

Пример работы LLL алгоритма. Красным изображён новый базис.

Все эти задачи разрешимы за полиномиальное время с помощью известного LLL-алгоритма изобретённого в 1982 году Арьеном Ленстрой, Хендриком Ленстрой и Ласло Ловасом.

В заданном базисе $𝐁=\{{𝐛}_1,{𝐛}_2,\dots ,{𝐛}_d\}$, с n-мерными целыми координатами, в решётке $L$ из ${ℝ}^n$, где $d\le n$, LLL-алгоритм находит более короткий (примерноШаблон:Уточнить) ортогональный базис за время:

$O(d^{5}n{\log }^{3}B)$,

где $B$ — это максимальная длина вектора $b_i$ в этом пространстве.

Основные криптографические конструкции и их стойкость

Шифрование

Шаблон:Нп3 — криптосистема основанная на CVP, а именно на односторонней функции с потайным входом опирающуюся на сложность редукции решётки. Была опубликована в 1997 году. Зная базис, можно сгенерировать вектор близкий к заданной точке, но зная это вектор нам необходим исходный базис, чтобы найти исходную точку. Алгоритм был проверен в 1999 году.

Реализация GGH

GGH состоит из открытого и секретного ключа.

Секретный ключ — это базис $B$ решётки $L$ и унимодулярная матрица $U$.

Открытый ключ — некоторый базис в решётке $L$ в виде $B^{\prime }=UB$.

Для некоторого $M$, пространство сообщения состоит из вектора $({\lambda }_1,...,{\lambda }_n)$, где $-M<{\lambda }_i<M$.

Шифрование

Задано сообщение $m=({\lambda }_1,...,{\lambda }_n)$, искажение $e$, открытый ключ $B^{\prime }$:

$v=\sum {\lambda }_i{b_i}^{\prime }$

В матричном виде:

$v=m\cdot B^{\prime }$.

$m$ состоит из целых значений, $b^{\prime }$ точка решётки, и v также точка решётки. Тогда шифротекст:

$c=v+e=m\cdot B^{\prime }+e$

Расшифрование

Для расшифрования необходимо вычислить:

$c\cdot B^{-1}=(m\cdot B^{\prime }+e)B^{-1}=m\cdot U\cdot B\cdot B^{-1}+e\cdot B^{-1}=m\cdot U+e\cdot B^{-1}$

Часть $e\cdot B^{-1}$ убирается, из соображений приближения. Сообщение:

$m=m\cdot U\cdot U^{-1}$

Пример

Выберем решётку $L\subset {ℝ}^2$ с базисом $B$:

$B=\left(\begin{array}{cc}7& 0\\ 0& 3\end{array}\right)$ и $B^{-1}=\left(\begin{array}{cc}\frac{1}{7}& 0\\ 0& \frac{1}{3}\end{array}\right)$

где

$U=\left(\begin{array}{cc}2& 3\\ 3& 5\end{array}\right)$ и

$U^{-1}=\left(\begin{array}{cc}5& -3\\ -3& 2\end{array}\right)$

В результате:

$B^{\prime }=UB=\left(\begin{array}{cc}14& 9\\ 21& 15\end{array}\right)$

Пусть сообщение $m=(3,-7)$ и вектор ошибки $e=(1,-1)$. Тогда шифротекст:

$c=m{B}^{\prime }+e=(-104,-79)$.

Для расшифровки необходимо вычислить:

$c{B}^{-1}=(\frac{-104}{7},\frac{-79}{3})$.

Округление даёт $(-15,-26)$ , восстановим сообщение:

$m=(-15,-26)U^{-1}=(3,-7)$.

NTRUEncrypt — криптосистема основанная на SVP, является альтернативой RSA и ECC. В вычислении используется кольцо многочленов.

Подпись

Схема подписи GGH впервые предложена 1995 году и опубликована в 1997 году Голдрихом, основана на сложности нахождения ближайшего вектора. Идея заключалась в использовании решёток, для которых «плохой» базис, векторы длинные и почти параллельные, является открытым и «хороший» базис с короткими и почти ортогональными векторами, является закрытым. По их методу, сообщение необходимо хешировать в пространство, натянутое на решётку, а подпись для данного хэша в этом пространстве является ближайшим узлом решётки. Схема не имела формального доказательства безопасности, и её базовый вариант был взломан в 1999 году Нгуэном (Nguyen). В 2006 году модифицированная версия была снова взломана Нгуэном и Реджевом (Regev).

NTRUSign — специальная, более эффективная версия подписи GGH, отличающаяся меньшим ключом и размером подписи. Она использует только решётки подмножества множества всех решёток, связанных с некоторыми полиномиальными кольцами. NTRUSign была предложена на рассмотрение в качестве стандарта IEEE P1363.1.