Схема шифрования 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]. Закрытым ключом является основание ${\displaystyle B}$ решетки ${\displaystyle L}$ с унимодулярной матрицей ${\displaystyle U}$.

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

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

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

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

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

${\displaystyle v=m\cdot B'}$

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

${\displaystyle c=v+e=m\cdot B'+e}$

Для расшифровки шифротекста вычисляется:

${\displaystyle 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}}$

Для удаления ${\displaystyle e\cdot B^{-1}}$, если он достаточно мал, используется метод округления Бабая^[5] .

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

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

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

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

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

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

${\displaystyle 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}}}$

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

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

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

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

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

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

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

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

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

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

Получаем:

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

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

${\displaystyle c=mB'+e=(-104,-79)}$

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

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

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

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

${\displaystyle 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.