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

Криптосистема Гольдрайха-Гольдвассера-Халеви (GGH) на основе решетки представляет собой асимметричную криптосистему, основанную на решетках . Существует также схема подписи GGH .

Криптосистема Гольдрайха-Гольдвассера-Халеви (GGH) использует тот факт, что задача ближайшего вектора может быть сложной задачей. Эта система была опубликована в 1997 году Одедом Гольдрейхом , Шафи Голдвассером и Шаем Халеви и использует одностороннюю функцию с люком , которая зависит от сложности сокращения решетки . Идея, заложенная в эту функцию-лазейку, заключается в том, что, имея любой базис решетки, легко сгенерировать вектор, близкий к точке решетки, например, взяв точку решетки и добавив небольшой вектор ошибок. Но чтобы вернуться от этого ошибочного вектора к исходной точке решетки, нужен специальный базис.

Схема шифрования GGH была криптоанализирована (взломана) в 1999 году Фонгом К. Нгуеном . Нгуен и Одед Регев провели криптоанализ соответствующей схемы подписи GGH в 2006 году.

Операция

GGH включает в себя закрытый ключ и открытый ключ .

Закрытый ключ является основой $B$ решетки $L$ с хорошими свойствами (такими как короткие почти ортогональные векторы) и унимодулярной матрицей $U$.

Открытый ключ — еще одна основа решетки. $L$ формы $B'=UB$.

Для некоторого выбранного M пространство сообщений состоит из вектора $(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}$

чтобы получить текст сообщения.

Пример

Позволять $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).\,$

Безопасность схемы

В 1999 году Нгуен показал, что схема шифрования GGH имеет конструктивный недостаток. Он показал, что каждый зашифрованный текст раскрывает информацию об открытом тексте и что проблему дешифрования можно превратить в специальную задачу ближайшего вектора, которую гораздо легче решить, чем общую CVP.

Библиография

• Гольдрейх, Одед; Гольдвассер, Шафи; Халеви, Шай (1997). «Криптосистемы с открытым ключом из задач редукции решетки». CRYPTO '97: Материалы 17-й ежегодной международной конференции по криптологии, посвящённой достижениям в криптологии . Лондон: Springer-Verlag. стр. 112–131.
• Нгуен, Фонг К. (1999). «Криптоанализ криптосистемы Гольдрайха – Гольдвассера – Халеви из Crypto '97» . CRYPTO '99: Материалы 19-й ежегодной международной конференции по криптологии, посвящённой достижениям в криптологии . Лондон: Springer-Verlag. стр. 288–304.
• Нгуен, Фонг К.; Регев, Одед (11 ноября 2008 г.). «Изучение параллелепипеда: криптоанализ подписей GGH и NTRU» (PDF) . Журнал криптологии . 22 (2): 139–160. дои : 10.1007/s00145-008-9031-0 . eISSN   1432-1378 . ISSN   0933-2790 . S2CID   2164840 . Предварительная версия в EUROCRYPT 2006.