Схе́ма шифрува́ння Го́лдрайха — Голдва́ссера — Галеві́, або скорочено ГГГ () — асиметрична криптосистема на основі ґраток. Існує також схема підпису Голдрайха — Гольдвассера — Галеві.
Криптосистема Голдрайха — Гольдвассера — Галеві використовує той факт, що найближча векторна проблема може бути важкою проблемою. Ця система була опублікована в 1997 році Одедом Голдрайхом, Шафі Голдвассер та Шаєм Галеві, і використовує односторонню функцію з секретом, яка спирається на складність зменшення ґратки. Ідея, закладена в цю функцію, полягає в тому, що, враховуючи будь-яку основу для ґратки, легко сформувати вектор, який знаходиться близько до точки ґратки, наприклад, взяти точку ґратки і додати невеликий вектор помилки. Але для повернення від цього помилкового вектору до вихідної точки ґратки потрібна спеціальна основа.
Схема шифрування ГГГ була криптоаналізована в 1999 році Фонгом Нгуєном.
Операція ГГГ передбачає приватний та відкритий ключі.
Приватний ключ є основою ґратки з хорошими властивостями (наприклад, короткими майже ортогональними векторами) та одномодульною матрицею .
Відкритий ключ — це ще одна основа ґратки форми .
Для деяких обраних простір повідомлень складається з вектору в діапазоні .
Шифрування Дано повідомлення , помилка та відкритий ключ обчислити:
,
У матричних позначеннях це:
.
Запам'ятайте складається з цілих значень, і — точка ґратки, отже, — це також точка ґратки. Тоді зашифрований текст:
.
Розшифровка Для розшифровки кіфертекту обчислюється:
,
Для вилучення терміну буде використана техніка Бабаї округлення поки він досить малий. Зрештою обчислити:
,
щоб отримати текст повідомлення.
Приклад Дозволяти бути ґраткою з основою і його обернено :
і
з
і ,
це дає:
.
Нехай буде повідомлення і вектор помилки . Тоді зашифрований текст:
Для розшифровки потрібно обчислити:
Це округляється до і повідомлення відновлюється за допомогою:
Безпека схеми У 1999 році Нгуєн на криптоконференції показав, що схема шифрування ГГГ має недолік у розробці схем. Нгуєн показав, що кожен зашифрований текст розкриває інформацію про відкритий текст і що проблема розшифровки може бути перетворена на спеціальну найближчу векторну задачу (НВЗ), набагато простішу для вирішення, ніж загальну НВЗ.
Див. також Криптосистема Міччанчо
Посилання
Бібліографія