Схема шифрования GGH

Схема шифрования GGH (англ. Goldreich–Goldwasser–Halevi) — асимметричная криптографическая система, основанная на решётках. Также существует схема подписи GGH.

Криптосистема опирается на решения задачи нахождения кратчайшего вектора и задачи нахождения ближайшего вектора. Схема шифрования GGH, опубликованная в 1997 году учёными Oded Goldreich, Shafi Goldwasser и Shai Halevi, использует одностороннюю функцию с потайным входом, ведь учитывая любой базис решётки, легко генерировать вектор, близкий к точке решётки. Например, взяв точку решётки и добавив небольшой вектор ошибки. Для возвращения из вектора ошибки в исходную точку решетки необходим специальный базис. В 1999 году Phong Q. Nguyen[1] сделал уточнение к оригинальной схеме шифрования GGH, что позволило решить четыре из пяти задачи GGH и получить частичную информацию о последней. Хотя GGH может быть безопасным при определенном выборе параметров, его эффективность по сравнению с традиционными криптосистемами с открытым ключом остается спорной[2]. Зачастую при шифровании требуется высокая размерность решётки, в то время как размер ключа растет примерно квадратично относительно размера решётки[2].

Единственной решётчатой схемой, которая справляется с высокими размерностями, является NTRU[3].

Алгоритм

GGH включает в себя открытый ключ и закрытый ключ[4]. Закрытым ключом является основание $B$ решетки $L$ с унимодулярной матрицей $U$ .

Открытый ключ является ещё одним основанием решётки $L$ вида $B'=UB$ .

Пусть пространство сообщений М состоит из векторов $(m_{1},...,m_{n})$ , принадлежащих интервалу $-M<m_{i}<M$ .

Шифрование

Дано сообщение $m=(m_{1},...,m_{n})$ , ошибка $e$ и открытый ключ $B'$ :

v=\sum m_{i}b_{i}'

В матричной записи:

v=m\cdot B'

Нужно помнить, что $m$ состоит из целочисленных значений, $b'$ является точкой решётки, поэтому $v$ также является точкой решётки. Тогда зашифрованный текст:

c=v+e=m\cdot B'+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}$ , если он достаточно мал, используется метод округления Бабая[5] .

Тогда, чтобы получить текст:

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

Анализ безопасности

В этом разделе рассматривается несколько способов атаки криптосистемы[6].

Атака округлением

Атака округлением — наиболее очевидная атака данной криптографической системы, кроме атаки грубой силы — поиска вектора ошибки $e.$ Ее суть заключается в использовании открытого ключа B для инвертирования функции таким же образом, как и при использовании закрытого ключа R. А именно, зная $c=B\cdot v+e$ , можно вычислить $B^{-1}\cdot c=v+B^{-1}\cdot e$ . Таким образом, можно найти вектор $d=B^{-1}\cdot e$ . При размерности ниже 80 LLL алгоритм способен правильно определять основание, однако начиная с размерности 100 и выше, данная атака хуже, чем тривиальный перебор вектора ошибок.

Атака штурмом

Данный алгоритм — очевидное уточнение атаки округлением. Здесь используется лучший алгоритм аппроксимации задачи кратчайших векторов. В частности, вместо алгоритма округления Babai используется алгоритм ближайшей плоскости. Он работает следующим образом. Дана точка $c$ и уменьшенный базиc $B$ = { ${b_{1}},\dots {b_{n}}$ } для LLL. Рассматриваются все аффинные пространства ${H_{k}}$ = { $k\cdot {b_{n}}$ + $\sum _{i=0}^{n-1}{a_{i}}\cdot {b_{i}}$ } : ${a_{i}}\in {\mathcal {R}}$ } . Для всех $k\in {\mathcal {Z}}$ находится гиперплоскость ${H_{k}}$ , ближайшая к точке $c$ . Далее на (n - 1)-мерное пространство, которое охватывается $B$ = { ${b_{1}},\dots {b_{n}}$ }, проектируется точка $c-k\cdot {b_{n}}$ . Это дает новую точку $c'$ и новый базис $B'$ = { ${b_{1}},\dots {b_{n}}$ }. Теперь алгоритм рекурсивно переходит к поиску точки $p'$ в этой (n - 1)-мерной решетки, близкой к $c'$ . Наконец, алгоритм устанавливает $p=p'+k\cdot {b_{n}}$ . Данный метод работает гораздо быстрее предыдущего. Тем не менее, его рабочая нагрузка также растет экспоненциально с размерностью решетки. Эксперименты показывают, что при использовании LLL в качестве алгоритма сокращения решетки требуется некоторое время на поиск, начиная с размеров 110-120. Атака становится неосуществимой, начиная с размеров 140-150.

Атака внедрения

Еще одним способом, который часто используется для аппроксимации задачи нахождения ближайшего вектора, является вложение n базисных векторов и точки $c$ , для которой необходимо найти близкую точку решетки в (n + 1)-мерной решетке

$B'={\begin{pmatrix}\vdots &\vdots &\vdots &\cdots &\vdots \\c&b_{1}&b_{2}&\cdots &b_{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&0&0&\cdots &0\end{pmatrix}}$

Затем используется алгоритм сокращения решетки для поиска кратчайшего ненулевого вектора в $L(B')$ , в надежде, что первые n элементов в этом векторе будут ближайшими точками к $c$ . Проведенные над этой атакой эксперименты (используя LLL как инструмент для поиска кратчайших векторов) указывают на то, что она работает до размерностей около 110-120, что лучше, чем атака округлением, которая становится хуже тривиального поиска уже после размерности равной 100.

Оценка атаки округлением

Пусть в каждом измерении $n$ создано пять закрытых базисов. Каждый базис выбирается как ${R_{i}}$ = $4\left|{\sqrt {n}}\right|\cdot I$ + rand $(\pm 4)$ , где I — тождественная матрица, а rand $(\pm 4)$ — квадратная матрица, члены которой выбираются равномерно из диапазона ${-4,...,4}$ . Для каждого базиса ${R_{i}}$ вычисляется значение ${\sigma _{i}}$ = $({\gamma _{i}}{\sqrt {8\ln({2n}/{\varepsilon })}})^{-1}$ , где ${\gamma _{i}}$ — евклидова норма наибольшей строки ${R_{i}}^{-1}$ , а $\varepsilon =10^{-5}$ . Для каждого закрытого базиса ${R_{i}}$ генерируется пять открытых базисов ${B_{ij}}$

${work-load_{ij}}$ = $({\pi }e)^{n/2}$ $\cdot {\sigma _{i}^{n}}$ $\cdot {\frac {orth-defect^{*}({B_{ij}})}{det|{B_{ij}}|}}$ , где $orth-defect^{*}$ — двойной дефект ортогональности: $orth-defect^{*}(B)=|det(B)|\cdot \prod _{i}\|{\hat {b_{i}}}\|,$ где ${\hat {b_{i}}}$ обозначает строку матрицы $B^{-1}$ .

Округление

Оценка атаки штурмом

Для оценки атаки штурмом использовались такие же открытый и закрытый базисы, как и в атаке округлением.

Штурм

Оценка атаки внедрением

Так как нельзя говорить о «рабочей нагрузке» атаки внедрением, было измерено максимальное значение ${\sigma }$ (связанное с вектором ошибок), для которого эта атака работает. Для этих экспериментов использовались те же закрытые базисы ${R}$ и открытые базисы ${B_{ij}}$ , что и для предыдущих двух атак. Затем использовался каждый открытый базис для оценки функции на нескольких точках, используя несколько различных значений $\sigma$ и проверялось, восстанавливает ли атака внедрения зашифрованное сообщение.

Внедрение

Пример

Пусть $L\subset \mathbb {R} ^{2}$ решетка с основанием $B$ и обратным ему $B^{-1}$ :

B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}

и

B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}

С унимодулярной матрицей:

U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix}}

и

U^{-1}={\begin{pmatrix}5&-3\\-3&2\\\end{pmatrix}}

Получаем:

B'=UB={\begin{pmatrix}14&9\\21&15\\\end{pmatrix}}

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

c=mB'+e=(-104,-79)

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

cB^{-1}=\left({\frac {-104}{7}},{\frac {-79}{3}}\right)

Это округляется до $(-15,-26).$

И сообщение восстанавливается с:

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

Источники и дополнительная литература

Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112—131, London, UK, 1997. Springer-Verlag.
Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97. In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288—304, London, UK, 1999. Springer-Verlag.

Примечания

Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97.. — С. 1-17.
Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97. С.— 1-2. (неопр.).
Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97. С.— 1. (неопр.).
Oded Goldreich, Shafi Goldwasser и Shai Halevi. [https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — С. 112-114.
Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97.. — С. 4.
Oded Goldreich, Shafi Goldwasser и Shai Halevi. [https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — С. 122-124.
Oded Goldreich, Shafi Goldwasser и Shai Halevi. [https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — С. 127-130.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97.. — С. 1-17.

[:0-2] Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97. С.— 1-2. (неопр.).

[3] Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97. С.— 1. (неопр.).

[4] Oded Goldreich, Shafi Goldwasser и Shai Halevi. [https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — С. 112-114.

[5] Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97.. — С. 4.

[6] Oded Goldreich, Shafi Goldwasser и Shai Halevi. [https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — С. 122-124.

[7] Oded Goldreich, Shafi Goldwasser и Shai Halevi. [https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — С. 127-130.