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

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

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

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

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

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

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

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

${\displaystyle 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]}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Недостатки

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

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

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

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

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

Шифрование

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

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

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

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

Для того, чтобы получить сумму текстов ${\displaystyle m_{1}}$ и ${\displaystyle m_{2}}$, достаточно сложить шифротексты и провести операцию расшифровывания. Действительно: ${\displaystyle {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 году на Смартом и Верткаутереном^[5]. Для реализации они выбрали схему с использованием идеальных решеток для простого определителя. Такие структуры представляются с помощью двух целых чисел (вне зависимости от их размера). Смарт и Верткаутерен предложили метод расшифровывания, в котором секретный ключ является одним целым числом. Таким образом, ученым удалось реализовать гомоморфную однородную схему, но они не смогли реализовать технику Джентри в случае достаточно больших параметров, а следовательно, им не удалось получить загружаемую и полностью гомоморфную схему.

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

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

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