Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Образовательные ресурсы:
Полностью гомоморфное шифрование I: теория и основы (преподаватель Ю Ю из Шанхайского университета Цзяо Тун)
Полностью гомоморфное шифрование II: теория и построение полностью гомоморфного шифрования (учитель Сян Се)

---

В настоящее время полностью гомоморфные схемы шифрования второго поколения (такие как BGV и BFV) и третьего поколения основаны на LWE. Теперь усовершенствованные полностью гомоморфные схемы также основаны на LWE, поэтому в этой статье обобщены базовые знания о LWE.
Сначала подумайте, мы хотим зашифровать число$с$, сейчас использую серию${а}_{я}$верно$с$Зашифруйте и получите${а}_{я}с$, на самом деле, ее можно решить, решив НОД наибольшего общего делителя$с$ .Однако если добавить случайный шум${е}_{я}$,получать${а}_{я}с+{е}_{я}$, то решить будет сложно$с$ ценить. Этот процесс — мое простое понимание LWE. Так называемая ошибка — это шум.

Процесс расчета полностью гомоморфного шифрования разделен на три этапа: генерация ключей KeyGen, шифрование Enc, гомоморфное вычисление Eval и дешифрование Dec. ,

Генератор ключей：

Сначала постройте приведенное выше уравнение,$с\cdot А+е=сА+е$, а затем получить открытый ключ pk ($-А$и$сА+е$сплайсинг) и закрытый ключ sk ($с$ и 1). Таким образом, получается, что результатом умножения pk и sk является случайный шум e (близкий к 0).

Прил.：

Открытый ключ pk, используемый для шифрования, r — это случайный вектор, содержащий только 0 или 1, а m — информация, подлежащая шифрованию (помещаемая в младший бит вектора).

Дек：

После вычисления внутреннего продукта закрытого ключа sk, используемого для расшифровки, и ct, найдите mod 2, чтобы получить результат расшифровки.

Доказательство правильности:

Умножьте sk и pk, чтобы получить 2e (условие, которому соответствует KeyGen), а затем выполните скалярное произведение с r, чтобы получить небольшой равномерный шум. Конечный результат — небольшой равномерный шум m+, поэтому шум можно устранить по модулю 2. Получить результат расшифровки m. Вот почему построенный шум равен 2e, а не e. Насколько я понимаю, создавая случайный шум с четным номером, удобно использовать мод 2 для устранения шума во время дешифрования.

Доказательство безопасности:

Когда pk псевдослучайен и r имеет достаточно высокую энтропию (т. е. случайность сильная?), и pk, и pk, умноженный на r, являются псевдослучайными. После сложения натуральных и векторов с m результат шифрования также будет псевдослучайным.

Ниже приводится шаблонное описание учителя Сян Се:
Формула шифрования: зашифрованный текст c = открытый ключ pk ✖️ случайный r + открытый текст m
Формула дешифрования: открытый текст m = <зашифрованный текст sk, закрытый ключ sk> mod q mod 2

На этом основании мод 2 можно использовать для расшифровки значения открытого текста m. Пока шум достаточно мал, точность может быть гарантирована.
Здесь необходимо кое-что отличить: приведенное выше$пК=(А,б=А{с}^{\prime }+2е)$— это решение BGV, а BFV — это$пК=(А,б=А{с}^{\prime }+е)$разница в том, что BGV кодирует информацию в младших битах, а BFV кодирует сообщения в старших битах (будет объяснено при изучении BFV).

Eval (аддитивный гомоморфизм и мультипликативный гомоморфизм):

Обратите внимание, что гомоморфное сложение или умножение приведет к значительному накоплению шума, а умножение имеет квадратичную тенденцию роста.
Затем давайте поговорим о том, как расшифровать результат гомоморфного умножения. Вы можете увидеть следующую формулу: Умножение двух зашифрованных текстов эквивалентно тензорному произведению зашифрованного текста и закрытого ключа соответственно, а затем внутреннему произведению. Таким образом, очевидно, что и зашифрованный текст, и закрытый ключ увеличились вдвое. Пример является доказательством эквивалентности.

Итак, вопрос в том, как восстановить размер зашифрованного текста и размер закрытого ключа после гомоморфного умножения? Эту проблему решает Key Switching.

Ниже приводится описание учителя Сян Се:

Переключение ключей

Цель состоит в том, чтобы восстановить размер зашифрованного текста и закрытого ключа до линейного размера.

Теперь найдем произведение шифртекстов c1 и c2:

Вышеописанный процесс основан на концепции битовой декомпозиции:

Ниже приводится описание учителя Сян Се:

Цель переключения ключей: преобразовать закрытый ключ.$\widetilde{с}$вниз$\widetilde{с}$ Преобразовать в закрытый ключ$с$вниз$с$,и$\widetilde{с}$и$с$Все они зашифрованы одним и тем же открытым текстом.
Основная концепция здесь — ключ переключения ключей (KSK), что означает использование закрытого ключа.$с$шифровать$\widetilde{с}$。

В процессе переключения ключей закрытый ключ может быть получен из$с\otimes с$стал линейным$с$, а зашифрованный текст меняется с$\widetilde{с}$стал линейным$с$ .И из последней строки формулы видно, что после переключения клавиш$⟨с,с⟩$и оригинал$⟨\widetilde{с},с\otimes с⟩$Существует разница в уровне шума между$2{\widetilde{с}}^{Т}\widetilde{е}$ , эта часть может быть очень большой! Таким образом, здесь пока нет возможности реализовать переключение клавиш.

Здесь представлена ​​матрица гаджета G:

Таким образом, процесс переключения ключей выглядит следующим образом:

На этом этапе добавленная ошибка очень мала.
Подводя итог, с помощью Key Switching, исходный закрытый ключ$\widetilde{с}=с\otimes с$вниз$\widetilde{с}=с\otimes с$, преобразуется в закрытый ключ$с$вниз$с$, обратите внимание на клавишу после переключения клавиш$с,с$Это не исходные значения (двойная проверка).

Для BGV шум сложения увеличивается линейно, а шум умножения увеличивается прямоугольно. Хотя переключение ключей может поддерживать умножение (ограничивая sk до чрезвычайно большого размера), на самом деле шум представляет собой очень небольшой шум, добавляемый к исходному шуму умножения. также очень велик. Следовательно, этот шум необходимо дополнительно снизить.

Уменьшение модуля

На данный момент вычисления гомоморфного умножения и сложения с небольшой глубиной реализованы посредством LWE. Переключение ключей использует новый ключ для каждого слоя. Однако по мере увеличения глубины вычислений расширение шума является взрывным, поэтому оно еще не нивелируется. . FHE (можно рассчитать FHE на заданной глубине).
Теперь мы надеемся реализовать FHE, который сможет рассчитывать определенную глубину без использования начальной загрузки, которая требует преобразования по модулю.

Я не совсем понимаю процесс посередине. Короче говоря, это преобразование зашифрованного текста c из домена по модулю q в домен по модулю p (p<).
Вот конкретный пример:
Если уменьшение модуля не выполнено, шум будет расти по двойной экспоненциальной тенденции по мере увеличения глубины, а ошибки дешифрования возникнут после уровня >= 3.

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

Итак, если вы хотите реализовать выравниваемый FHE, вы можете установить модуль${Б}^{г}$, то вы сможете вычислить глубину$г$схема (где$Б$ — верхняя граница шума обновленного зашифрованного текста).Рассчитано$г$После глубины модуль следует уменьшить до$Б$ , чтобы гарантировать отсутствие ошибок при расшифровке на данный момент. BGV — это уровневый FHE.