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

Схема шифрования GGH (Шаблон:Lang-en) — асимметричная криптографическая система, основанная на решётках. Также существует схема подписи GGH.

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

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

Алгоритм

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

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

Пусть пространство сообщений М состоит из векторов $(m_1,\mathrm{...},m_n)$, принадлежащих интервалу $-M<m_i<M$.

Шифрование

Дано сообщение $m=(m_1,\mathrm{...},m_n)$, ошибка $e$ и открытый ключ $B^{\prime }$:

$v=\sum m_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}$

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

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

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

Атака округлением — наиболее очевидная атака данной криптографической системы, кроме атаки грубой силы — поиска вектора ошибки $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 ℛ$} . Для всех $k\in 𝒵$ находится гиперплоскость $H_k$, ближайшая к точке $c$. Далее на (n - 1)-мерное пространство, которое охватывается $B$ = {$b_1,\dots b_n$}, проектируется точка $c-k\cdot b_n$. Это дает новую точку $c^{\prime }$и новый базис $B^{\prime }$ = {$b_1,\dots b_n$}. Теперь алгоритм рекурсивно переходит к поиску точки $p^{\prime }$ в этой (n - 1)-мерной решетки, близкой к $c^{\prime }$. Наконец, алгоритм устанавливает $p=p^{\prime }+k\cdot b_n$. Данный метод работает гораздо быстрее предыдущего. Тем не менее, его рабочая нагрузка также растет экспоненциально с размерностью решетки. Эксперименты показывают, что при использовании LLL в качестве алгоритма сокращения решетки требуется некоторое время на поиск, начиная с размеров 110-120. Атака становится неосуществимой, начиная с размеров 140-150.

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

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

$B^{\prime }=\left(\begin{array}{ccccc}⋮& ⋮& ⋮& \cdots & ⋮\\ c& b_1& b_2& \cdots & b_n\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& 0& 0& \cdots & 0\end{array}\right)$

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

Оценка эффективности атак

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

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

$work-loa{d}_{ij}$ = $(\pi e{)}^{n/2}$$\cdot {\sigma }_i^n$$\cdot \frac{orth-defec{t}^{\ast }(B_{ij})}{det|B_{ij}|}$, где $orth-defec{t}^{\ast }$ — двойной дефект ортогональности: $orth-defec{t}^{\ast }(B)=|det(B)|\cdot \prod _i\Vert \widehat{b_i}\Vert ,$ где $\widehat{b_i}$ обозначает строку матрицы $B^{-1}$.

Округление

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

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

Штурм

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

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

Внедрение

Пример

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

$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).$

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

• 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.