WikiDer > HEAAN

эта статья является сирота, как никакие другие статьи ссылка на это. Пожалуйста ввести ссылки на эту страницу из Статьи по Теме; попробуйте Инструмент поиска ссылок для предложений. (Ноябрь 2019)

HEAAN (Гомоморфное шифрование для арифметики приближенных чисел) является открытым исходным кодом гомоморфное шифрование (HE) библиотека, реализующая приближенную схему HE, предложенную Cheon, Ким, Ким и Сон (CKKS).^[1]Первая версия HEAAN была опубликована на GitHub^[2] 15 мая 2016 г., а позже - новая версия HEAAN с самонастройка алгоритм^[3]На данный момент последняя версия - Версия 2.1.

Пространство открытого текста CKKS

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

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

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

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

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

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

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

• ${ displaystyle { text {Dcd}} (m_ {1} + m_ {2}; Delta) приблизительно { vec {z}} _ {1} + { vec {z}} _ {2}}$,
• ${ displaystyle { text {Dcd}} (m_ {1} cdot m_ {2}; Delta) приблизительно { vec {z}} _ {1} circ { vec {z}} _ {2 }}$,

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

Алгоритмы

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

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

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

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

Шифрование

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

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

Расшифровка

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

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

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

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

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

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

Правильность сохраняется как ${ displaystyle { text {Dec}} (sk, ct _ { text {add}}) приблизительно { text {Dec}} (sk, ct) + { text {Dec}} (sk, ct ') }$.

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

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

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

Правильность сохраняется как ${ displaystyle { text {Dec}} (sk, ct _ { text {mult}}) приблизительно { text {Dec}} (sk, ct) cdot { text {Dec}} (sk, ct ' )}$.

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

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

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

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

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

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

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

Библиотека

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

использованная литература