ХОРОШИЙ
Разработчик(и) | Лаборатория криптографии в Сеульском национальном университете |
---|---|
Первоначальный выпуск | 15 мая 2016 г |
Репозиторий | |
Написано в | С++ |
Тип | Гомоморфное шифрование |
Лицензия | CC BY-NC 3.0 |
HEAAN ( гомоморфное шифрование для арифметики приближенных чисел ) — это библиотека гомоморфного шифрования (HE) с открытым исходным кодом, которая реализует приблизительную схему HE, предложенную Чеоном , Кимом, Кимом и Сонгом (CKKS). [1] Первая версия HEAAN опубликована на GitHub. [2] 15 мая 2016 г., а затем новая версия HEAAN с начальной загрузки. алгоритмом [3] был освобожден.На данный момент последней версией является версия 2.1. [4] [ нужна проверка ]
Открытое текстовое пространство CKKS
[ редактировать ]В отличие от других схем HE, схема CKKS поддерживает приблизительную арифметику над комплексными числами (следовательно, действительными числами). Точнее, пространство открытого текста схемы CKKS: для некоторого целого числа степени двойки . Чтобы эффективно работать со сложным вектором открытого текста, Cheon et al. предложенные методы кодирования/декодирования открытого текста, использующие кольцевой изоморфизм .
Метод кодирования
[ редактировать ]Учитывая вектор открытого текста и коэффициент масштабирования вектор открытого текста кодируется как полином путем вычисления где обозначает функцию округления по коэффициентам.
Метод декодирования
[ редактировать ]Учитывая полином сообщения и коэффициент масштабирования полином сообщения декодируется в комплексный вектор путем вычисления .
Здесь коэффициент масштабирования позволяет нам контролировать ошибку кодирования/декодирования, возникающую в процессе округления. А именно, можно получить приближенное уравнение контролируя где и обозначают алгоритм кодирования и декодирования соответственно.
Из свойства кольцевой изоморфности отображения , для и , имеют место следующие утверждения:
- ,
- ,
где обозначает произведение Адамара векторов одинаковой длины.Эти свойства гарантируют приблизительную корректность вычислений в закодированном состоянии при масштабном коэффициенте выбирается соответствующим образом.
Алгоритмы
[ редактировать ]Схема CKKS в основном состоит из этих алгоритмов: генерация ключей, шифрование, дешифрование, гомоморфное сложение и умножение, а также изменение масштаба. Для положительного целого числа , позволять быть частным кольцом модуль . Позволять , и быть распределениями по который выводит полиномы с небольшими коэффициентами. Эти распределения, начальный модуль , а размер кольца предопределены до этапа генерации ключей.
Генерация ключей
[ редактировать ]Алгоритм генерации ключей следующий:
- Пример секретного полинома .
- Образец (соответственно ) однородный случайным образом из (соответственно ), и .
- Вывод секретного ключа , открытый ключ и ключ оценки .
Шифрование
[ редактировать ]Алгоритм шифрования следующий:
- Образец эфемерного секретного полинома .
- Для данного полинома сообщения , вывести зашифрованный текст .
Расшифровка
[ редактировать ]Алгоритм расшифровки следующий:
- Для заданного зашифрованного текста , вывести сообщение .
В результате расшифровки выводится приблизительное значение исходного сообщения, т.е. , а ошибка аппроксимации определяется выбором распределений . При рассмотрении гомоморфных операций ошибки оценки также включаются в ошибку аппроксимации. Основные гомоморфные операции — сложение и умножение — выполняются следующим образом.
Гомоморфное сложение
[ редактировать ]Алгоритм гомоморфного сложения следующий:
- Учитывая два зашифрованных текста и в , выход .
Корректность сохраняется как .
Гомоморфное умножение
[ редактировать ]Алгоритм гомоморфного умножения следующий:
- Учитывая два зашифрованных текста и в , вычислить . Выход .
Корректность сохраняется как .
Обратите внимание, что ошибка аппроксимации (в сообщении) экспоненциально растет с увеличением количества гомоморфных умножений. Чтобы преодолеть эту проблему, в большинстве схем HE обычно используется метод переключения модуля, который был предложен Бракерски, Джентри и Вайкунтанатаном. [5] В случае HEAAN процедура переключения модуля называется изменением масштаба. Алгоритм масштабирования очень прост по сравнению с оригинальным алгоритмом Бракерски-Джентри-Вайкунтанатана.При применении алгоритма масштабирования после гомомоморфного умножения ошибка аппроксимации растет линейно, а не экспоненциально.
Изменение масштаба
[ редактировать ]Алгоритм масштабирования следующий:
- Учитывая зашифрованный текст и новый модуль , выведите масштабированный зашифрованный текст .
Общая процедура схемы CKKS следующая: Каждый вектор открытого текста который состоит из комплексных (или действительных) чисел, сначала кодируется как полином методом кодирования, а затем зашифрован в виде зашифрованного текста . После нескольких гомоморфных операций полученный зашифрованный текст расшифровывается как полином. а затем декодируется как вектор открытого текста что является конечным результатом.
Безопасность
[ редактировать ]Безопасность IND -CPA схемы CKKS основана на предположении о сложности задачи кольцевого обучения с ошибками (RLWE), кольцевого варианта очень многообещающей сложной задачи обучения на основе решетки (LWE).В настоящее время наиболее известными атаками для RLWE через круговое кольцо степени двойки являются общие атаки LWE, такие как двойная атака и первичная атака.Битовая безопасность схемы CKKS, основанной на известных атаках, оценивалась с помощью оценщика LWE Альбрехта. [6]
Библиотека
[ редактировать ]На данный момент выпущены версии 1.0, 1.1 и 2.1. Версия 1.0 — это первая реализация схемы CKKS без начальной загрузки.Во второй версии был добавлен алгоритм начальной загрузки, чтобы пользователи могли выполнять крупномасштабные гомоморфные вычисления.В версии 2.1, на данный момент последней версии, умножение элементов кольца в было ускорено за счет использования (NTT), оптимизированной для быстрого преобразования Фурье (БПФ) реализации теоретико-числового преобразования .
Ссылки
[ редактировать ]- ^ Чхон, Чон Хи; Ким, Андрей; Ким, Миран; Сон, Ёнсу (2017). «Гомоморфное шифрование для арифметики приближенных чисел». Такаги Т., Пейрин Т. (редакторы) Достижения в криптологии – ASIACRYPT 2017 . ASIACRYPT 2017. Спрингер, Чам. стр. 409–437. дои : 10.1007/978-3-319-70694-8_15 .
- ^ Андрей Ким; Кёхён Хан; Миран Ким; Ёнсу Сон. «Примерная библиотека HE HEAAN» . Проверено 15 мая 2016 г.
- ^ Чон Хи Чхон , Кёхён Хан, Андрей Ким, Миран Ким и Ёнсу Сон. Начальная загрузка для приближенного гомоморфного шифрования . В EUROCRYPT 2018 (весна) .
- ^ snucrypto/HEAAN , Лаборатория криптографии Сеульского национального университета, 19 июля 2021 г. , получено 20 июля 2021 г.
- ^ З. Бракерски, К. Джентри и В. Вайкунтанатан. Полностью гомоморфное шифрование без начальной загрузки . В ИТКС 2012 г.
- ^ Мартин Альбрехт. Оценки безопасности для задачи обучения с ошибками, https://bitbucket.org/malb/lwe-estimator