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

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

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

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

$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]$, где $d=det(J)$ и r — корень для $f_{n}(x)$ по модулю d.

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

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

$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]$

1. Вычисляется инверсия для $v(x)$ по модулю $f_{n}(x)$, то есть многочлен $w(x)$ степени не более n-1, что $v(x)*w(x)=const{\bmod {f}}_{n}(x)$. Тогда матрица

$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]$

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

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

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

Шифрование

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

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

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

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

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

$b=a{\bmod {2}}=(c{\bmod {V}}){\bmod {2}}=(c*(W/d)){\bmod {2}}$

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

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

Стойкость

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

Недостатки

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

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

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

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

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

Шифрование

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

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

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

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

Для того, чтобы получить сумму текстов $m_{1}$ и $m_{2}$, достаточно сложить шифротексты и провести операцию расшифровывания. Действительно: ${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}}$

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

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

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

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

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

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