Схема шифрування Голдрайха — Голдвассера — Галеві

Схе́ма шифрува́ння Го́лдрайха — Голдва́ссера — Галеві́, або скорочено ГГГ (англ. Goldreich–Goldwasser–Halevi(GGH)) — асиметрична криптосистема на основі ґраток. Існує також схема підпису Голдрайха — Гольдвассера — Галеві.

Криптосистема Голдрайха — Гольдвассера — Галеві використовує той факт, що найближча векторна проблема може бути важкою проблемою. Ця система була опублікована в 1997 році Одедом Голдрайхом, Шафі Голдвассер та Шаєм Галеві, і використовує односторонню функцію з секретом, яка спирається на складність зменшення ґратки. Ідея, закладена в цю функцію, полягає в тому, що, враховуючи будь-яку основу для ґратки, легко сформувати вектор, який знаходиться близько до точки ґратки, наприклад, взяти точку ґратки і додати невеликий вектор помилки. Але для повернення від цього помилкового вектору до вихідної точки ґратки потрібна спеціальна основа.

Схема шифрування ГГГ була криптоаналізована в 1999 році Фонгом Нгуєном.

Операція

ГГГ передбачає приватний та відкритий ключі.

Приватний ключ є основою $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 році Нгуєн на криптоконференції показав, що схема шифрування ГГГ має недолік у розробці схем. Нгуєн показав, що кожен зашифрований текст розкриває інформацію про відкритий текст і що проблема розшифровки може бути перетворена на спеціальну найближчу векторну задачу (НВЗ), набагато простішу для вирішення, ніж загальну НВЗ.

Див. також

• Криптосистема Міччанчо

Посилання

• Uth, Max. Benezit Dictionary of Artists. Oxford University Press. 31 жовтня 2011. doi:10.1093/benz/9780199773787.article.b00187394.

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

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997). Public-key cryptosystems from lattice reduction problems. CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology. London: Springer-Verlag. с. 112—131.
• Nguyen, Phong Q. (1999). Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto ’97. CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology. London: Springer-Verlag. с. 288—304.