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

В Гольдрайх – Гольдвассер – Галеви (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.