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

В Гольдрайх – Гольдвассер – Галеви (GGH) решетчатый криптосистема является асимметричный криптосистема на основе решетки. Также есть Схема подписи GGH.

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

Схема шифрования GGH была подвергнута криптоанализу в 1999 году Фонгом К. Нгуеном.

Операция

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

Приватный ключ - это основа ${displaystyle B}$ решетки ${displaystyle L}$ с хорошими свойствами (например, короткие почти ортогональный векторов) и a унимодулярная матрица ${displaystyle U}$.

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

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

Шифрование

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

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

В матричных обозначениях это

${displaystyle v = mcdot B '}$.

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

${displaystyle c = v + e = mcdot B '+ e}$

Расшифровка

Чтобы расшифровать шифротекст, вычисляют

${displaystyle ccdot B ^ {- 1} = (mcdot B ^ {prime} + e) ​​B ^ {- 1} = mcdot Ucdot Bcdot B ^ {- 1} + ecdot B ^ {- 1} = mcdot U + ecdot B ^ {- 1}}$

Метод округления Бабая будет использован для удаления термина ${displaystyle ecdot B ^ {- 1}}$ пока он достаточно мал. Наконец вычислить

${displaystyle m = mcdot Ucdot U ^ {- 1}}$

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

Пример

Позволять ${displaystyle Lsubset mathbb {R} ^ {2}}$ - решетка с базисом ${displaystyle B}$ и его обратное ${displaystyle B ^ {- 1}}$

${displaystyle B = {egin {pmatrix} 7 & 0 0 & 3 end {pmatrix}}}$ и ${displaystyle B ^ {- 1} = {egin {pmatrix} {frac {1} {7}} & 0 0 & {frac {1} {3}} end {pmatrix}}}$

С

${displaystyle U = {egin {pmatrix} 2 & 3 3 & 5 end {pmatrix}}}$ и

${displaystyle U ^ {- 1} = {egin {pmatrix} 5 & -3 -3 & 2 end {pmatrix}}}$

это дает

${displaystyle B '= UB = {egin {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}} ight).}$

Это округляется до ${displaystyle (-15, -26)}$ и сообщение восстанавливается с помощью

${displaystyle m = (- 15, -26) U ^ {- 1} = (3, -7).,}$

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

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

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

• Гольдрайх, Одед; Гольдвассер, Шафи; Халеви, Шай (1997). «Криптосистемы с открытым ключом от задач редукции решетки». CRYPTO ’97: Материалы 17-й ежегодной международной криптологической конференции по достижениям в криптологии. Лондон: Springer-Verlag. С. 112–131.
• Нгуен, Фонг К. (1999). «Криптоанализ криптосистемы Голдрайха – Гольдвассера – Галеви от Crypto '97». CRYPTO ’99: Материалы 19-й ежегодной международной криптологической конференции по достижениям в криптологии. Лондон: Springer-Verlag. С. 288–304.