Русская Википедия:Криптосистема Джентри

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

Для схемы используются Шаблон:Iw J в цепочках многочленов по модулю <math>f_{n}(x) = x^{n} +1</math>. Эрмитова нормальная форма идеальной решётки имеет вид:

<math>HNF(J) = \quad\left[\begin{array}{ccccc} d & 0 & 0 & 0 & 0 \\ -r & 1 & 0 & 0 & 0 \\ -[r^2]_d & 0 & 1 & 0 & 0\\ -[r^2]_d & 0 & 0 & 0 & 0\\ \vdots & & & \ddots & \\ -[r^{n-1}]_d & 0 & 0 & 0 & 1 \end{array}\right]</math>, где <math>d = det(J)</math> и r — корень для <math>f_n(x)</math> по модулю d.

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

1. Выбирается произвольная n-мерная целочисленная решётка v, где каждый вход <math>v_i</math> выбирается наугад, как t-разрядное число. С помощью этого вектора v формально определяется многочлен <math>v(x) = \sum_{i \mathop =0}^{n-1} v_{i}x^{i}</math>, а также соответствующая матрица поворота:

<math>V = \quad\left[\begin{array}{ccccc} v_0 & v_1 & v_2 & & v_{n-1} \\ -v_{n-1} & v_0 & v_1 & & v_{n-2} \\ -v_{n-2} & v_{n-1} & v_0 & & v_{n-3}\\ & & & \ddots & \\ -v_1 & -v_2 & -v_3 & & v_0 \end{array}\right]</math>

1. Вычисляется инверсия для <math>v(x)</math> по модулю <math>f_n(x)</math>, то есть многочлен <math>w(x)</math> степени не более n-1, что <math>v(x) * w(x) = const \bmod f_n(x)</math>. Тогда матрица

<math>W = \quad\left[\begin{array}{ccccc} w_0 & w_1 & w_2 & & w_{n-1} \\ -w_{n-1} & w_0 & w_1 & & w_{n-2} \\ -w_{n-2} & w_{n-1} & w_0 & & w_{n-3}\\ & & & \ddots & \\ -w_1 & -w_2 & -w_3 & & w_0 \end{array}\right]</math>

является инверсией для <math>V</math>, то есть <math>V * W = const * I</math>, где <math>I</math> — единичная матрица.

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

Открытым ключом будет являться матрица <math>V</math>, заданная числами r и d. Закрытым ключом будут являться два многочлена <math>(v, w)</math>.

Шифрование

Пусть требуется зашифровать бит <math>{m\in (0,1)}</math>

На входе имеется бит b и открытый ключ V. Выбирается шумовой вектор <math>u</math>, компоненты которого принимают значения 0,1,-1. Затем вычисляется вектор <math>a = 2*u + b*e_{1}</math>, а шифротекст вычисляется по формуле <math>c = a \bmod V = a - ([a * V^{-1}] * V)</math>

Здесь для базиса V пространства L и данного вектора c выражение <math> c \bmod V</math> используется для обозначения вектора <math>c' \in P(V)</math> такого, что <math>c - c' \in L</math>

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

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

<math> b = a \bmod 2 = (c \bmod V) \bmod 2 = (c * (W/d)) \bmod 2 </math>

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

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

Стойкость

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

Недостатки

Существенным недостатком данной схемы является то, что выполнение вычислений приводит к накоплению ошибки и, после того как она превышает <math>p</math>, расшифровать сообщение становится невозможным. Одним из вариантов решения данной проблемы является повторное шифрование данных после некоторого количества операций, однако такой вариант снижает производительность вычислений и требует постоянного доступа к секретному ключу.

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

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

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

1. Выбирается число <math>n</math>, по модулю которого будет работать схема.
2. Выбирается секретный ключ <math>sk</math> — случайное число, много большее <math>n</math>, такое, что НОД<math>{(sk, n) = 1}</math>
3. Выбирается публичный ключ <math>pk</math> — набор больших чисел <math>[a_{1},..a_{i}]</math>, таких, что <math>a_{i} = r * sk + e * n</math>, где <math>r</math> — небольшое случайное число, <math>e</math> — произвольное случайное число.

Шифрование

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

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

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

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

Для того, чтобы получить сумму текстов <math>m_{1}</math> и <math>m_{2}</math>, достаточно сложить шифротексты и провести операцию расшифровывания. Действительно: <math>{D(E(m_{1}, pk) + E(m_{2}, pk)) = D(m_{1} + m_{2} + \sum_{i \mathop =0}^n C_{i}pk_{i}) = D(m_{1} + m_{2} + C_{1}^{'}sk + C_{2}^{'}n) = m_{1} + m_{2}}</math>

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

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

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

Основным препятствием в данной реализации являлась сложность генерации ключей для однородных схем: прежде всего, схемы должны генерировать очень большое количество «кандидатов» для поиска ключа, для которого определитель будет простым — может понадобиться вплоть до <math>{n^{1,5}}</math> кандидатов при работе со структурами размерности <math>n</math>. Кроме того, даже после нахождения оптимального варианта, сложность вычислений секретного ключа, соответствующего этой структуре равна, по крайней мере, <math>{{\tilde {O}}(n^{2,5})}</math> для решёток размерности <math>n</math>. По этим причинам ученым не удалось сгенерировать ключи размерностей <math>{n>2048}</math>. Кроме того, Смарт и Веркаутерен оценили, что многочлен расшифровки будет иметь степень в несколько сотен, а это требует для процедуры с их параметрами использования решётки размерностью не менее <math>{n=2^{27}}</math><math>{(\approx 1,3\times 10^{8})}</math>, что значительно превышает вычислительные возможности процедуры генерации ключей.

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

В 2011 году Крейг Джентри вместе с Шайем Халеви представил практическую реализацию для полностью гомоморфной схемы шифрования по аналогии с используемой в более ранних работах схемой Смарта и Верткаутерена. Основная оптимизация состоит в методе генерации ключей для основного относительно гомоморфного шифрования, не требующем полной инверсии многочленов. Это снижает асимптотическую сложность от <math>{{\tilde {O}}(n^{2,5})}</math> до <math>{{\tilde {O}}(n^{1,5})}</math> при работе с <math>n</math> размерными решетками (и на практике сокращает время расчетов от многих часов до нескольких минут).