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

Криптосистема на основе решеток Goldreich –Goldwasser–Halevi (GGH) — это сломанная асимметричная криптосистема на основе решеток . Существует также схема подписи GGH , которая не была взломана по состоянию на 2024 год.

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

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

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

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

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

Для некоторого выбранного M пространство сообщений состоит из вектора в диапазоне .${\displaystyle (м_{1},...,м_{н})}$${\displaystyle -M<m_{i}<M}$

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

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

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

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

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

${\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 L\subset \mathbb {R} ^{2}}$${\displaystyle Б}$${\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).\,}$

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

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (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. doi :10.1007/s00145-008-9031-0. eISSN  1432-1378. ISSN  0933-2790. S2CID  2164840.Предварительная версия в EUROCRYPT 2006.