Схема шифрования GGH (V]ybg onsjkfgunx GGH)

Перейти к навигации Перейти к поиску

Схема шифрования GGH (англ. Goldreich–Goldwasser–Halevi) — асимметричная криптографическая система, основанная на решётках. Также существует схема подписи GGH.

Криптосистема опирается на решения задачи нахождения кратчайшего вектора и задачи нахождения ближайшего вектора. Схема шифрования GGH, опубликованная в 1997 году учёными Oded Goldreich, Shafi Goldwasser и Shai Halevi, использует одностороннюю функцию с потайным входом, ведь учитывая любой базис решётки, легко генерировать вектор, близкий к точке решётки. Например, взяв точку решётки и добавив небольшой вектор ошибки. Для возвращения из вектора ошибки в исходную точку решетки необходим специальный базис. В 1999 году Phong Q. Nguyen[1] сделал уточнение к оригинальной схеме шифрования GGH, что позволило решить четыре из пяти задачи GGH и получить частичную информацию о последней. Хотя GGH может быть безопасным при определенном выборе параметров, его эффективность по сравнению с традиционными криптосистемами с открытым ключом остается спорной[2]. Зачастую при шифровании требуется высокая размерность решётки, в то время как размер ключа растет примерно квадратично относительно размера решётки[2].

Единственной решётчатой схемой, которая справляется с высокими размерностями, является NTRU[3].

GGH включает в себя открытый ключ и закрытый ключ[4]. Закрытым ключом является основание решетки с унимодулярной матрицей .

Открытый ключ является ещё одним основанием решётки вида .

Пусть пространство сообщений М состоит из векторов , принадлежащих интервалу .

Шифрование

[править | править код]

Дано сообщение , ошибка и открытый ключ :

В матричной записи:

Нужно помнить, что состоит из целочисленных значений, является точкой решётки, поэтому также является точкой решётки. Тогда зашифрованный текст:

Расшифровка

[править | править код]

Для расшифровки шифротекста вычисляется:

Для удаления , если он достаточно мал, используется метод округления Бабая[5] .

Тогда, чтобы получить текст:

Анализ безопасности

[править | править код]

В этом разделе рассматривается несколько способов атаки криптосистемы[6].

Атака округлением

[править | править код]

Атака округлением — наиболее очевидная атака данной криптографической системы, кроме атаки грубой силы — поиска вектора ошибки Ее суть заключается в использовании открытого ключа B для инвертирования функции таким же образом, как и при использовании закрытого ключа R. А именно, зная , можно вычислить . Таким образом, можно найти вектор . При размерности ниже 80 LLL алгоритм способен правильно определять основание, однако начиная с размерности 100 и выше, данная атака хуже, чем тривиальный перебор вектора ошибок.


Атака штурмом

[править | править код]

Данный алгоритм — очевидное уточнение атаки округлением. Здесь используется лучший алгоритм аппроксимации задачи кратчайших векторов. В частности, вместо алгоритма округления Babai используется алгоритм ближайшей плоскости. Он работает следующим образом. Дана точка и уменьшенный базиc = {} для LLL. Рассматриваются все аффинные пространства = {+} : } . Для всех находится гиперплоскость , ближайшая к точке . Далее на (n - 1)-мерное пространство, которое охватывается = {}, проектируется точка . Это дает новую точку и новый базис = {}. Теперь алгоритм рекурсивно переходит к поиску точки в этой (n - 1)-мерной решетки, близкой к . Наконец, алгоритм устанавливает . Данный метод работает гораздо быстрее предыдущего. Тем не менее, его рабочая нагрузка также растет экспоненциально с размерностью решетки. Эксперименты показывают, что при использовании LLL в качестве алгоритма сокращения решетки требуется некоторое время на поиск, начиная с размеров 110-120. Атака становится неосуществимой, начиная с размеров 140-150.

Атака внедрения

[править | править код]

Еще одним способом, который часто используется для аппроксимации задачи нахождения ближайшего вектора, является вложение n базисных векторов и точки , для которой необходимо найти близкую точку решетки в (n + 1)-мерной решетке

Затем используется алгоритм сокращения решетки для поиска кратчайшего ненулевого вектора в , в надежде, что первые n элементов в этом векторе будут ближайшими точками к . Проведенные над этой атакой эксперименты (используя LLL как инструмент для поиска кратчайших векторов) указывают на то, что она работает до размерностей около 110-120, что лучше, чем атака округлением, которая становится хуже тривиального поиска уже после размерности равной 100.

Оценка эффективности атак[7]

[править | править код]

Оценка атаки округлением

[править | править код]

Пусть в каждом измерении создано пять закрытых базисов. Каждый базис выбирается как = + rand, где I — тождественная матрица, а randквадратная матрица, члены которой выбираются равномерно из диапазона . Для каждого базиса вычисляется значение = , где евклидова норма наибольшей строки , а . Для каждого закрытого базиса генерируется пять открытых базисов

= , где — двойной дефект ортогональности: где обозначает строку матрицы .

Округление

Оценка атаки штурмом

[править | править код]

Для оценки атаки штурмом использовались такие же открытый и закрытый базисы, как и в атаке округлением.

Штурм

Оценка атаки внедрением

[править | править код]

Так как нельзя говорить о «рабочей нагрузке» атаки внедрением, было измерено максимальное значение (связанное с вектором ошибок), для которого эта атака работает. Для этих экспериментов использовались те же закрытые базисы и открытые базисы , что и для предыдущих двух атак. Затем использовался каждый открытый базис для оценки функции на нескольких точках, используя несколько различных значений и проверялось, восстанавливает ли атака внедрения зашифрованное сообщение.

Внедрение

Пусть решетка с основанием и обратным ему :

и

С унимодулярной матрицей:

и

Получаем:

Пусть сообщение и вектор ошибок Тогда зашифрованный текст:

Для расшифровки необходимо:

Это округляется до

И сообщение восстанавливается с:

Источники и дополнительная литература

[править | править код]
  • Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112—131, London, UK, 1997. Springer-Verlag.
  • Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97. In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288—304, London, UK, 1999. Springer-Verlag.

Примечания

[править | править код]
  1. Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97.. — С. 1-17. Архивировано 16 июля 2018 года.
  2. 1 2 Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97. С.— 1-2. Архивировано 16 июля 2018 года.
  3. Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97. С.— 1. Архивировано 16 июля 2018 года.
  4. Oded Goldreich, Shafi Goldwasser и Shai Halevi. [https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — С. 112-114. Архивировано 4 мая 2019 года.
  5. Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97.. — С. 4. Архивировано 16 июля 2018 года.
  6. Oded Goldreich, Shafi Goldwasser и Shai Halevi. [https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — С. 122-124. Архивировано 4 мая 2019 года.
  7. Oded Goldreich, Shafi Goldwasser и Shai Halevi. [https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Public-Key Cryptosystems from Lattice Reduction Problems]. — С. 127-130. Архивировано 4 мая 2019 года.