ХОРОШИЙ

ХОРОШИЙ

Разработчик(и)	Лаборатория криптографии в Сеульском национальном университете
Первоначальный выпуск	15 мая 2016 г ( 15 мая 2016 )
Репозиторий	github .с /snucrypto /ХОРОШИЙ
Написано в	С++
Тип	Гомоморфное шифрование
Лицензия	CC BY-NC 3.0

HEAAN ( гомоморфное шифрование для арифметики приближенных чисел ) — это библиотека гомоморфного шифрования (HE) с открытым исходным кодом, которая реализует приблизительную схему HE, предложенную Чеоном , Кимом, Кимом и Сонгом (CKKS). Первая версия HEAAN опубликована на GitHub. 15 мая 2016 г., а затем новая версия HEAAN с начальной загрузки. алгоритмом был освобожден.На данный момент последней версией является версия 2.1.

Открытое текстовое пространство CKKS

В отличие от других схем HE, схема CKKS поддерживает приблизительную арифметику над комплексными числами (следовательно, действительными числами). Точнее, пространство открытого текста схемы CKKS: $\mathbb {C} ^{n/2}$ для некоторого целого числа степени двойки $n$. Чтобы эффективно работать со сложным вектором открытого текста, Cheon et al. предложенные методы кодирования/декодирования открытого текста, использующие кольцевой изоморфизм $\phi :\mathbb {R} [X]/(X^{n}+1)\rightarrow \mathbb {C} ^{n/2}$.

Метод кодирования

Учитывая вектор открытого текста ${\vec {z}}=(z_{1},z_{2},...,z_{n/2})\in \mathbb {C} ^{n/2}$ и коэффициент масштабирования $\Delta >1$вектор открытого текста кодируется как полином $m(X)\in R:=\mathbb {Z} [X]/(X^{n}+1)$путем вычисления $m(X)=\lfloor \Delta \cdot \phi ^{-1}({\vec {z}})\rceil \in R$ где $\lfloor \cdot \rceil$ обозначает функцию округления по коэффициентам.

Метод декодирования

Учитывая полином сообщения $m(X)\in R$ и коэффициент масштабирования $\Delta >1$полином сообщения декодируется в комплексный вектор ${\vec {z}}\in \mathbb {C} ^{n/2}$ путем вычисления ${\vec {z}}=\Delta ^{-1}\cdot \phi (m(X))\in \mathbb {C} ^{n/2}$.

Здесь коэффициент масштабирования $\Delta >1$ позволяет нам контролировать ошибку кодирования/декодирования, возникающую в процессе округления. А именно, можно получить приближенное уравнение ${\text{Dcd}}({\text{Ecd}}({\vec {z}};\Delta );\Delta )\approx {\vec {z}}$ контролируя $\Delta$ где ${\text{Ecd}}$ и ${\text{Dcd}}$ обозначают алгоритм кодирования и декодирования соответственно.

Из свойства кольцевой изоморфности отображения $\phi :\mathbb {R} [X]/(X^{n}+1)\rightarrow \mathbb {C} ^{n/2}$, для $m_{1}={\text{Ecd}}({\vec {z}}_{1};\Delta )$ и $m_{2}={\text{Ecd}}({\vec {z}}_{2};\Delta )$, имеют место следующие утверждения:

• ${\text{Dcd}}(m_{1}+m_{2};\Delta )\approx {\vec {z}}_{1}+{\vec {z}}_{2}$,
• ${\text{Dcd}}(m_{1}\cdot m_{2};\Delta )\approx {\vec {z}}_{1}\circ {\vec {z}}_{2}$,

где $\circ$ обозначает произведение Адамара векторов одинаковой длины.Эти свойства гарантируют приблизительную корректность вычислений в закодированном состоянии при масштабном коэффициенте $\Delta$ выбирается соответствующим образом.

Алгоритмы

Схема CKKS в основном состоит из этих алгоритмов: генерация ключей, шифрование, дешифрование, гомоморфное сложение и умножение, а также изменение масштаба. Для положительного целого числа $q$, позволять $R_{q}:=R/qR$ быть частным кольцом $R$ модуль $q$. Позволять $\chi _{s}$, $\chi _{r}$ и $\chi _{e}$ быть распределениями по $R$ который выводит полиномы с небольшими коэффициентами. Эти распределения, начальный модуль $Q$, а размер кольца $n$ предопределены до этапа генерации ключей.

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

Алгоритм генерации ключей следующий:

• Пример секретного полинома $s\leftarrow \chi _{s}$.
• Образец $a$ (соответственно $a'$) однородный случайным образом из $R_{Q}$ (соответственно $R_{PQ}$), и $e,e'\leftarrow \chi _{e}$.
• Вывод секретного ключа $sk\leftarrow (1,s)\in R_{Q}^{2}$, открытый ключ $pk\leftarrow (b=-a\cdot s+e,a)\in R_{Q}^{2}$и ключ оценки $evk\leftarrow (b'=-a'\cdot s+e'+P\cdot s^{2},a')\in R_{PQ}^{2}$.

Шифрование

Алгоритм шифрования следующий:

• Образец эфемерного секретного полинома $r\leftarrow \chi _{r}$.
• Для данного полинома сообщения $m\in R$, вывести зашифрованный текст $ct\leftarrow (c_{0}=r\cdot b+e_{0}+m,c_{1}=r\cdot a+e_{1})\in R_{Q}^{2}$.

Расшифровка

Алгоритм расшифровки следующий:

• Для заданного зашифрованного текста $ct\in R_{q}^{2}$, вывести сообщение $m'\leftarrow \langle ct,sk\rangle$ $({\text{mod }}q)$.

В результате расшифровки выводится приблизительное значение исходного сообщения, т.е. ${\text{Dec}}(sk,{\text{Enc}}(pk,m))\approx m$, а ошибка аппроксимации определяется выбором распределений $\chi _{s},\chi _{e},\chi _{r}$. При рассмотрении гомоморфных операций ошибки оценки также включаются в ошибку аппроксимации. Основные гомоморфные операции — сложение и умножение — выполняются следующим образом.

Гомоморфное сложение

Алгоритм гомоморфного сложения следующий:

• Учитывая два зашифрованных текста $ct$ и $ct'$ в $R_{q}^{2}$, выход $ct_{\text{add}}\leftarrow ct+ct'\in R_{q}^{2}$.

Корректность сохраняется как ${\text{Dec}}(sk,ct_{\text{add}})\approx {\text{Dec}}(sk,ct)+{\text{Dec}}(sk,ct')$.

Гомоморфное умножение

Алгоритм гомоморфного умножения следующий:

• Учитывая два зашифрованных текста $ct=(c_{0},c_{1})$ и $ct'=(c_{0}',c_{1}')$ в $R_{q}^{2}$, вычислить $(d_{0},d_{1},d_{2})=(c_{0}c_{0}',c_{0}c_{1}'+c_{1}c_{0}',c_{1}c_{1}')$ $({\text{mod }}q)$. Выход $ct_{\text{mult}}\leftarrow (d_{0},d_{1})+\lfloor P^{-1}\cdot d_{2}\cdot evk\rceil \in R_{q}^{2}$.

Корректность сохраняется как ${\text{Dec}}(sk,ct_{\text{mult}})\approx {\text{Dec}}(sk,ct)\cdot {\text{Dec}}(sk,ct')$.

Обратите внимание, что ошибка аппроксимации (в сообщении) экспоненциально растет с увеличением количества гомоморфных умножений. Чтобы преодолеть эту проблему, в большинстве схем HE обычно используется метод переключения модуля, который был предложен Бракерски, Джентри и Вайкунтанатаном. В случае HEAAN процедура переключения модуля называется изменением масштаба. Алгоритм масштабирования очень прост по сравнению с оригинальным алгоритмом Бракерски-Джентри-Вайкунтанатана.При применении алгоритма масштабирования после гомомоморфного умножения ошибка аппроксимации растет линейно, а не экспоненциально.

Изменение масштаба

Алгоритм масштабирования следующий:

• Учитывая зашифрованный текст $ct\in R_{q}^{2}$ и новый модуль $q'<q$, выведите масштабированный зашифрованный текст $ct_{\text{rs}}\leftarrow \lfloor (q'/q)\cdot ct\rceil \in R_{q'}^{2}$.

Общая процедура схемы CKKS следующая: Каждый вектор открытого текста ${\vec {z}}$ который состоит из комплексных (или действительных) чисел, сначала кодируется как полином $m(X)\in R$ методом кодирования, а затем зашифрован в виде зашифрованного текста $ct\in R_{q}^{2}$. После нескольких гомоморфных операций полученный зашифрованный текст расшифровывается как полином. $m'(X)\in R$ а затем декодируется как вектор открытого текста ${\vec {z}}'$ что является конечным результатом.

Безопасность

Безопасность IND -CPA схемы CKKS основана на предположении о сложности задачи кольцевого обучения с ошибками (RLWE), кольцевого варианта очень многообещающей сложной задачи обучения на основе решетки (LWE).В настоящее время наиболее известными атаками для RLWE через круговое кольцо степени двойки являются общие атаки LWE, такие как двойная атака и первичная атака.Битовая безопасность схемы CKKS, основанной на известных атаках, оценивалась с помощью оценщика LWE Альбрехта.

Библиотека

На данный момент выпущены версии 1.0, 1.1 и 2.1. Версия 1.0 — это первая реализация схемы CKKS без начальной загрузки.Во второй версии был добавлен алгоритм начальной загрузки, чтобы пользователи могли выполнять крупномасштабные гомоморфные вычисления.В версии 2.1, на данный момент последней версии, умножение элементов кольца в $R_{q}$ было ускорено за счет использования (NTT), оптимизированной для быстрого преобразования Фурье (БПФ) реализации теоретико-числового преобразования .