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

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

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

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

$HNF(J)=\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\\ ⋮& & & \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=0}^{n-1}{v}_i{x}^i$, а также соответствующая матрица поворота:

$V=\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{modf}_n(x)$. Тогда матрица

$W=\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=amodV=a-([a*V^{-1}]*V)$

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

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

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

$b=amod2=(cmodV)mod2=(c*(W/d))mod2$

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

Шифрование является гомоморфным относительно операций сложения и умножения. Для того, чтобы выполнить сложение или умножение шифротекстов, необходимо выполнить эти операции в базисе 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=0}^n{C}_{i}p{k}_i)=D(m_1+m_2+C_1^{\text{'}}sk+C_2^{\text{'}}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$ размерными решетками (и на практике сокращает время расчетов от многих часов до нескольких минут).