Криптосистема Джентри

Криптосистема Джентри (от фамилии создателя Крейга Джентри) — первая возможная конструкция для полностью гомоморфной криптосистемы, основанная на криптографии на решетках. Впервые была предложена Крейгом Джентри в 2009 году[1] и являлась темой его докторской диссертации. Схема Джентри поддерживает операции сложения и умножения над шифротекстом, что позволяет построить кольца для реализации любых произвольных вычислений. Впоследствии имела множество доработок и модификаций с целью улучшения её производительности.

Описание алгоритма

править

Для схемы используются[2] идеальные решётки J в цепочках многочленов по модулю  . Эрмитова нормальная форма идеальной решётки имеет вид[2]:

 , где   и r — корень для   по модулю d.

Генерация ключей[2]

  1. Выбирается произвольная n-мерная целочисленная решётка v, где каждый вход   выбирается наугад, как t-разрядное число. С помощью этого вектора v формально определяется многочлен  , а также соответствующая матрица поворота:

 

  1. Вычисляется инверсия для   по модулю  , то есть многочлен   степени не более n-1, что  . Тогда матрица

 

является инверсией для  , то есть  , где   — единичная матрица.

  1. Также проверяется, что Эрмитова нормальная форма для   имеет вид, указанный выше, а именно все столбцы, кроме левого, образуют единичную матрицу. В таком случае вся матрица   может быть получена с помощью элементов r и d.

Открытым ключом будет являться матрица  , заданная числами r и d. Закрытым ключом будут являться два многочлена  .

Шифрование[2]

Пусть требуется зашифровать бит  

На входе имеется бит b и открытый ключ V. Выбирается шумовой вектор  , компоненты которого принимают значения 0,1,-1. Затем вычисляется вектор  , а шифротекст вычисляется по формуле[2]  

Здесь для базиса V пространства L и данного вектора c выражение   используется для обозначения вектора   такого, что  [2]

Расшифровывание[2]

На входе имеется вектор С и матрицы V и W. Исходный бит b получается в результате операции:

 

Гомоморфность[2]

Шифрование является гомоморфным относительно операций сложения и умножения. Для того, чтобы выполнить сложение или умножение шифротекстов, необходимо выполнить эти операции в базисе V

Стойкость[3]

Защищенность своей схемы Джентри обосновал двумя проблемами: проблемой сложности худшего случая криптографии на идеальных решетках и задачей о сумме подмножеств. Обе задачи являются  -сложными, поэтому стойкость системы сводится к  -сложной задаче.

Недостатки

Существенным недостатком данной схемы является то, что выполнение вычислений приводит к накоплению ошибки[4] и, после того как она превышает  , расшифровать сообщение становится невозможным. Одним из вариантов решения данной проблемы является повторное шифрование данных после некоторого количества операций, однако такой вариант снижает производительность вычислений и требует постоянного доступа к секретному ключу[3].

Упрощённая схема Джентри

править

Рассматривается схема, гомоморфная относительно только операции сложения[4].

Генерация ключей

  1. Выбирается число  , по модулю которого будет работать схема.
  2. Выбирается секретный ключ   — случайное число, много большее  , такое, что НОД 
  3. Выбирается публичный ключ   — набор больших чисел  , таких, что  , где   — небольшое случайное число,   — произвольное случайное число.

Шифрование

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

Расшифровывание

На входе имеется шифротекст и числа   и  . Вычисляется последовательно остаток от деления шифротекста на   и на  . Результатом будет являться исходное сообщение.

Гомоморфность

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

Плюсом данной схемы является простота реализации и малая потребность в ресурсах. К минусам можно отнести конечное множество публичных ключей и лишь частичную гомоморфность.

Реализация Смарта и Верткаутерена

править

Первая попытка реализовать схему Джентри была сделана в 2010 году на Смартом и Верткаутереном[5]. Для реализации они выбрали схему с использованием идеальных решеток для простого определителя. Такие структуры представляются с помощью двух целых чисел (вне зависимости от их размера). Смарт и Верткаутерен предложили метод расшифровывания, в котором секретный ключ является одним целым числом. Таким образом, ученым удалось реализовать гомоморфную однородную схему, но они не смогли реализовать технику Джентри в случае достаточно больших параметров, а следовательно, им не удалось получить загружаемую и полностью гомоморфную схему.

Основным препятствием в данной реализации являлась сложность генерации ключей для однородных схем: прежде всего, схемы должны генерировать очень большое количество «кандидатов» для поиска ключа, для которого определитель будет простым — может понадобиться вплоть до   кандидатов при работе со структурами размерности  . Кроме того, даже после нахождения оптимального варианта, сложность вычислений секретного ключа, соответствующего этой структуре равна, по крайней мере,   для решёток размерности  . По этим причинам ученым не удалось сгенерировать ключи размерностей  . Кроме того, Смарт и Веркаутерен оценили, что многочлен расшифровки будет иметь степень в несколько сотен, а это требует для процедуры с их параметрами использования решётки размерностью не менее   , что значительно превышает вычислительные возможности процедуры генерации ключей[2].

Полностью гомоморфная схема Джентри

править

В 2011 году Крейг Джентри вместе с Шайем Халеви представил[2] практическую реализацию для полностью гомоморфной схемы шифрования по аналогии с используемой в более ранних работах схемой Смарта и Верткаутерена. Основная оптимизация состоит в методе генерации ключей для основного относительно гомоморфного шифрования, не требующем полной инверсии многочленов. Это снижает асимптотическую сложность от   до   при работе с   размерными решетками (и на практике сокращает время расчетов от многих часов до нескольких минут).

Примечания

править
  1. Craig Gentry. "A FULLY HOMOMORPHIC ENCRYPTION SCHEME" Архивная копия от 5 февраля 2017 на Wayback Machine A dissertation submitted to the department of computer science and the committee on graduate students of Standford University, 2009.
  2. 1 2 3 4 5 6 7 8 9 10 Craig Gentry and Shai Halevi. "Implementing Gentry’s Fully-Homomorphic Encryption Scheme" Архивная копия от 22 декабря 2017 на Wayback Machine IBM research.
  3. 1 2 Трубей А.И. ГОМОМОРФНОЕ ШИФРОВАНИЕ: БЕЗОПАСНОСТЬ ОБЛАЧНЫХ ВЫЧИСЛЕНИЙ И ДРУГИЕ ПРИЛОЖЕНИЯ (ОБЗОР). Информатика. 2015;(1):90-101.
  4. 1 2 Алумян А.С., Глазунов И.А., Тишин В.В. "Гомоморфное шифрование" Архивная копия от 22 декабря 2017 на Wayback Machine Статья для XXI Международной научно-практической конференции «Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ» (Россия, г. Новосибирск, 18 мая 2017 г.)
  5. N. P. SmartF. Vercauteren. "Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes" Архивная копия от 22 декабря 2017 на Wayback Machine, 2010.