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

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

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

Алгоритм

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

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

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

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

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

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

Атака округлением — наиболее очевидная атака данной криптографической системы, кроме атаки грубой силы — поиска вектора ошибки ${\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}}}$ } для . Рассматриваются все аффинные пространства ${\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}}}$ . Данный метод работает гораздо быстрее предыдущего. Тем не менее, его рабочая нагрузка также растет экспоненциально с размерностью решетки. Эксперименты показывают, что при использовании в качестве алгоритма сокращения решетки требуется некоторое время на поиск, начиная с размеров 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}$ . Проведенные над этой атакой эксперименты (используя как инструмент для поиска кратчайших векторов) указывают на то, что она работает до размерностей около 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.

Примечания