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

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

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

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

Алгоритм

GGH включает в себя открытый ключ и закрытый ключ. Закрытым ключом является основание $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}$, если он достаточно мал, используется метод округления Бабая .

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

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

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

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

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

Атака округлением — наиболее очевидная атака данной криптографической системы, кроме атаки грубой силы — поиска вектора ошибки $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.