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

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

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

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

Алгоритм

GGH включает в себя открытый ключ и закрытый ключ. Закрытым ключом является основание [math]\displaystyle{ B }[/math] решетки [math]\displaystyle{ L }[/math] с унимодулярной матрицей [math]\displaystyle{ U }[/math].

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

Пусть пространство сообщений М состоит из векторов [math]\displaystyle{ (m_1,..., m_n) }[/math], принадлежащих интервалу [math]\displaystyle{ -M \lt m_i \lt M }[/math].

Шифрование

Дано сообщение [math]\displaystyle{ m = (m_1,..., m_n) }[/math], ошибка [math]\displaystyle{ e }[/math] и открытый ключ [math]\displaystyle{ B' }[/math]:

[math]\displaystyle{ v = \sum m_i b_i' }[/math]

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

[math]\displaystyle{ v=m\cdot B' }[/math]

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

[math]\displaystyle{ c=v+e=m \cdot B' + e }[/math]

Расшифровка

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

[math]\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} }[/math]

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

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

[math]\displaystyle{ m = m \cdot U \cdot U^{-1} }[/math]

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

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

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

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

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

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

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

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

[math]\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} }[/math]

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

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

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

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

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

Округление

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

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

Штурм

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

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

Внедрение

Пример

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

[math]\displaystyle{ B= \begin{pmatrix} 7 & 0 \\ 0 & 3 \\ \end{pmatrix} }[/math] и [math]\displaystyle{ B^{-1}= \begin{pmatrix} \frac{1}{7} & 0 \\ 0 & \frac{1}{3} \\ \end{pmatrix} }[/math]

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

[math]\displaystyle{ U = \begin{pmatrix} 2 & 3 \\ 3 &5\\ \end{pmatrix} }[/math] и

[math]\displaystyle{ U^{-1} = \begin{pmatrix} 5 & -3 \\ -3 &2\\ \end{pmatrix} }[/math]

Получаем:

[math]\displaystyle{ B' = U B = \begin{pmatrix} 14 & 9 \\ 21 & 15 \\ \end{pmatrix} }[/math]

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

[math]\displaystyle{ c = m B'+e=(-104, -79) }[/math]

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

[math]\displaystyle{ c B^{-1} = \left( \frac{-104}{7}, \frac{-79}{3}\right) }[/math]

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

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

[math]\displaystyle{ m= (-15, -26) U^{-1} = (3, -7).\, }[/math]

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

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