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

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

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

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

Операція

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

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

Відкритий ключ — це ще одна основа ґратки ${\displaystyle L}$ форми ${\displaystyle B'=UB}$.

Для деяких обраних ${\displaystyle M}$ простір повідомлень складається з вектору ${\displaystyle (m_{1},...,m_{n})}$ в діапазоні ${\displaystyle -M<m_{i}<M}$.

Шифрування

Дано повідомлення ${\displaystyle m=(m_{1},...,m_{n})}$, помилка ${\displaystyle e}$ та відкритий ключ ${\displaystyle B'}$ обчислити:

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

У матричних позначеннях це:

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

Запам'ятайте ${\displaystyle m}$ складається з цілих значень, і ${\displaystyle b'}$ — точка ґратки, отже, ${\displaystyle v}$ — це також точка ґратки. Тоді зашифрований текст:

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

Див. також

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

Посилання

• 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.