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

Схе́ма шифрува́ння Го́лдрайха — Голдва́ссера — Галеві́, або скорочено ГГГ (Шаблон:Lang-en) — асиметрична криптосистема на основі ґраток. Існує також схема підпису Голдрайха — Гольдвассера — Галеві.

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

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

Операція

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

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

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

Для деяких обраних $M$ простір повідомлень складається з вектору $(m_1,...,m_n)$ в діапазоні $-M<m_i<M$.

Шифрування

Дано повідомлення $m=(m_1,...,m_n)$, помилка $e$ та відкритий ключ $B^{\prime }$ обчислити:

$v=\sum m_i{b_i}^{\prime }$,

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

$v=m\cdot B^{\prime }$.

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

$c=v+e=m\cdot B^{\prime }+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 {ℝ}^2$ бути ґраткою з основою $B$ і його обернено $B^{-1}$:

$B=\left(\begin{array}{cc}7& 0\\ 0& 3\end{array}\right)$ і $B^{-1}=\left(\begin{array}{cc}\frac{1}{7}& 0\\ 0& \frac{1}{3}\end{array}\right)$

з

$U=\left(\begin{array}{cc}2& 3\\ 3& 5\end{array}\right)$ і

$U^{-1}=\left(\begin{array}{cc}5& -3\\ -3& 2\end{array}\right)$,

це дає:

$B^{\prime }=UB=\left(\begin{array}{cc}14& 9\\ 21& 15\end{array}\right)$.

Нехай буде повідомлення $m=(3,-7)$ і вектор помилки $e=(1,-1)$. Тоді зашифрований текст:

$c=m{B}^{\prime }+e=(-104,-79).$

Для розшифровки потрібно обчислити:

$c{B}^{-1}=(\frac{-104}{7},\frac{-79}{3}).$

Це округляється до $(-15,-26)$ і повідомлення відновлюється за допомогою:

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

Безпека схеми

У 1999 році Нгуєн на криптоконференції показав, що схема шифрування ГГГ має недолік у розробці схем. Нгуєн показав, що кожен зашифрований текст розкриває інформацію про відкритий текст і що проблема розшифровки може бути перетворена на спеціальну найближчу векторну задачу (НВЗ), набагато простішу для вирішення, ніж загальну НВЗ.

Див. також

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

Посилання

• Шаблон:Cite book

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

• Шаблон:Cite book
• Шаблон:Cite book