Гомоморфное шифрование: классификация шифров и аппаратные ускорители / forpes.ru

Главная
Гомоморфное шифрование: классификация шифров и аппаратные ускорители

Гомоморфное шифрование: классификация шифров и аппаратные ускорители +2

05.10.2025 07:17

VoyakaGOD 0 249 Источник

Всем доброго времени суток. Я студент 4-го курса бакалавриата МФТИ. В рамках курса по защите информации я написал эссе на тему гомоморфного шифрования и решил, поделиться им здесь, поскольку эта тема не так часто обсуждается на Хабре. Кроме того, я делаю это, надеясь дать окружающим пищу для размышлений и самому узнать что-то новое по данной теме.

1 Введение

С ростом объёма обрабатываемых данных возникает потребность в облачных и распределённых вычислениях. Обычное шифрование позволяет защитить данные во время передачи, но для вычислений данные должны быть открыты. Этого можно избежать, используя шифрование, задающее гомоморфное отображение:

$E(a) \circ_1 E(b) = E(a \circ_2 b)$

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

2 Классификация гомоморфных шифров

2.1 Детерминированность

2.1.1 Детерминированные

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

2.1.2 Недетерминированные

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

2.2 Объём поддерживаемых операций

2.2.1 PHE

PHE(Partially Homomorphic Encryption) - частично гомоморфные шифры поддерживают только одну операцию. Их можно условно разделить на два подтипа по виду поддерживаемой операции на аддитивные и мультипликативные.

2.2.2 SHE

SHE(Somewhat Homomorphic Encryption) - ограниченно гомоморфные шифры поддерживают несколько различных операций, но ограниченное количество раз.
Это вызвано наличием случайного шума при недетерминированных шифровании.

2.2.3 FHE

FHE(Fully Homomorphic Encryption) - полностью гомоморфные шифры поддерживают несколько различных операций без ограничений на количество применений. Это достигается введением операции bootstrapping.

2.3 Тип сообщения

2.3.1 Бинарные

$m \in \{0,1\}$

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

2.3.2 Целочисленные

$m \in \mathbb{Z}_q$

Такие схемы позволяют выполнять точные арифметические операции по модулю шифрования .

2.3.3 Приближённые схемы

$m \in \mathbb{R}$

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

3 Решётки

Определения решётки, SVP, LWE, RLWE взяты из [1].

3.1 Определение

Пусть $B = \{\vec{b}_1, \dots, \vec{b}_k \}$ - система независимых векторов в $\mathbb{R}^n$ , тогда множество $\mathcal{L} = \{\sum\limits_{i=1}^k \alpha_i \vec{b}_i \;|\; \alpha_i \in \mathbb{Z} \}$ называется -мерной решёткой с базисом .

3.2 SVP

SVP(Shortest vector problem) состоит в нахождении ненулевого вектора $\vec{v}$ наименьшей длины $\lambda_1(\mathcal{L})= ||\vec{v}||$ в решётке $\mathcal{L}$ . Рост размерности решётки приводит к экспоненциальному росту возможных векторов. На данный момент все алгоритмы решения SVP имею сложность . Кроме того не найдено алгоритмов для быстрого решения SVP на квантовых компьютерах.

Эту задачу можно обобщить, пусть задано $\gamma > 1$ , тогда $\gamma$ -SVP состоит в отыскании ненулевого $\vec{v} \in \mathcal{L}$ , такого, что $||\vec{v}|| < \gamma \lambda_1(\mathcal{L})$ .

3.3 LWE

Пусть есть секретный вектор $\vec{s} \in \mathbb{Z}_q^n$ , случайные векторы $\vec{a}_i \in \mathbb{Z}_q^n$ и небольшой шум $e_i \in \mathbb{Z}_q$ , тогда
можно поставить задачу LWE(Learning with errors), которая лежит в основе большинства современных алгоритмов гомоморфного шифрования, и состоит в отыскании $\vec{s}$ при условии, что нам известны некоторые пары $(\vec{a}_i, b_i)$ , $b_i = \vec{a}_i \cdot \vec{s} + e_i$ .

Одед Реджев доказал [2], что решение $\gamma$ -SVP можно свести к LWE. Следовательно квантовые компьютеры пока не умеют быстро решать LWE. И, таким образом, алгоритмы шифрования, построенные на LWE, являются постквантовыми.

3.4 RLWE

RLWE - это постановка задачи LWE для факторколец $R_q = \mathbb{Z}_q[x]/(f(x))$ , где $f(x) \in \mathbb{Z}_q[x]$ - неприводимый многочлен степени и - простое число.

В RLWE заданы многочлены $a_i(x), s(x), e_i(x) \in R_q$ , нам известны пары , и нужно найти .

4 Bootstrapping

В то время как детерминированные шифры могут быть полезны в контексте баз данных(SQL запросы), для приватных вычислений используются в основном именно недетерминированные(рандомизированные) шифры. Но у них есть недостаток, при выполнении операций над шифротекстом накапливается шум, что при большом количестве вычислений делает расшифровку невозможной. Эта проблема решается с помощью операции называемой bootstrapping(обновление), которая пересчитывает шифротекст, убирая лишний шум. Обновление шифротекста происходит на стороне вычислителя и не требует знание ключа, что позволяет создать FHE.
Идея состоит в том, чтобы гомоморфно провести цепочку расшифрования с помощью доступных операций.

Минусом является огромная вычислительная сложность этой операции. Например для шифра TFHE:

$E(m) = (\vec{a}, c) = (\vec{a}, \vec{a} \cdot \vec{s} + \frac{m}{2} + e)$ $m = D(c) = Round(2(c - \vec{a} \cdot \vec{s}))$ $c^* = Bootstrap(c, E(s)) = E(Round(2(c - \vec{a} \cdot \vec{s})))$

Здесь появляется функция округления, именно она и делает вычисление bootstrapping крайне медленным.

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

5 Примеры гомоморфных шифров

5.1 чистый RSA

$E(m) = m^e \bmod n$

Здесь (модуль RSA) и (открытая экспонента) образуют публичный ключ .

Легко заметить свойство, делающее RSA детерминированным мультипликативным PHE:

$\left[ E(m_1)*E(m_2) \right] \bmod n = E(m_1*m_2)$

5.2 Paillier

$E(m) = g^m r^n \bmod n^2$

Здесь - открытый ключ, - случайный шум.

$\left[ E(m_1)*E(m_2) \right] \bmod n^2 = E(m_1+m_2)$

То есть, данный шифр является недетерминированным аддитивным PHE. В своей статье [3] Паскаль Паилье доказал, что шум никак не влияет на расшифровку сообщения.

5.3 ElGamal

$E(m) = (a, b), \; a = g^k \bmod p, \; b = m*y^k \bmod p$

Здесь - открытый ключ, - случайный шум, - генератор группы $\mathbb{Z}_p^* = <g>$ .

$E(m_1) \circ E(m_2) = (a_1,b_1) \circ (a_2,b_2) = ([a_1*a_2] \bmod p, [b_1*b_2] \bmod p)$ $E(m_1) \circ E(m_2) = (g^{k_1+k_2} \bmod p, m_1*m_2*y^{k_1+k_2} \bmod p) = E(m_1*m_2)$

Таким образом, ElGamal является недетерминированным мультипликативным PHE. И в отличие от Paillier, здесь шум линейно накапливается, ограничивая количество допустимых операций.

5.4 Gentry

До этого мы рассматривали алгоритмы для сообщений целочисленного типа, теперь обсудим схему, которая работает с отдельными битами сообщения $m \in \{0, 1\}$ .

$E(m) = (\vec{a},b), \; b = \left[\vec{a} \cdot \vec{s} + 2e + m \right] \bmod q$

Здесь $\vec{a} \in \mathbb{Z}_q^n$ - открытый вектор, $\vec{s} \in \mathbb{Z}_q^n$ - секретный вектор и $e \in \mathbb{Z}_q$ - шум.

Gentry является первой полностью гомоморфной схемой шифрования, именно Крейг Джентри придумал операцию bootstrapping.

Базовыми операциями являются xor и and:

$E(m_1 \oplus m_2) = \left[E(m_1) + E(m_2)\right] \bmod q$ $E(m_1 \land m_2) = \left[E(m_1) * E(m_2)\right] \bmod q$

Из них легко получить стандартный набор логических операций not, and, or:

$E(m_1 \lor m_2) = E(m_1 \oplus m_2 \oplus (m_1 \land m_2))$ $E(\overline{m}) = E(1 \oplus m) = \left[E(1) + E(m)\right] \bmod q$

Gentry является недетерминированным FHE, поэтому мы можем, не беспокоясь, раскрыть один из возможных шифров единицы .

6 Современные гомоморфные шифры

6.1 BFV

Фиксируем модуль шифротекста и модуль открытого текста $t \ll Q$ .

Тогда можно определить масштабирующий фактор $\Delta = \left\lfloor \frac{Q}{t} \right\rfloor$ и кольца $R = \mathbb{Z}[x]/(x^N+1), \; R_Q = R/QR$ .

Выберем секретный ключ $s \in R_Q$ и случайные полиномы $a,e \in R_Q$ , тогда открытый ключ в BFV(Brakerski/Fan-Vercauteren) имеет вид $pk = (as+e,-a) \in R_Q^2$

При шифровании нужно сначала представить сообщение как элемент кольца $m \in R_Q$ и затем вычислить функцию шифрования:

$E(m) = (\Delta \cdot [m]_t + u \cdot pk_0 + e_0, u \cdot pk_1 + e_1)$

BFV является недетерминированным полностью гомоморфным шифром, но он устроен сложнее, чем ранее разобранные шифры, и при выполнении умножения используется процедура релинеаризации [4].

6.2 BGV

Алгоритм BGV(Brakerski-Gentry-Vaikuntanathan) также основан на LRWE, но в отличие от BFV вместо смены ключа здесь используется многомодульная система(после операции умножения уменьшаем модуль $Q_L \rightarrow Q_{L-1} \rightarrow \dots \rightarrow Q_1 \rightarrow Q_0$ ) [4].

6.3 TFHE

Рассмотрим множество $\mathbb{T} = \mathbb{R}/\mathbb{Z}$ , которое представляет собой полуинтервал с операциями по модулю единицы. Это множество называют тором, отсюда и название шифра TFHE(fast fully homomorphic encryption scheme over the torus). Данный шифр работает с бинарными сообщениями $m \in \{0,1\}$ следующим образом:

$E(m) = (a, \left[a \cdot s + \frac{m}{2} + e \right] \bmod 1) \in \mathbb{T}^{n+1}$

Где $a \in \mathbb{T}^n$ - случайный вектор, $s \in \{0,1\}^n$ - секретный ключ.

$E(m_1 \oplus m_2) = \left[E(m_1) + E(m_2)\right] \bmod 1$

Для реализации and в TFHE используются PBS(programmable bootstrapping) и LUT(lookup table) [5]:

$E(m_1 \land m_2) = PBS(E(m_1), LUT(f)), \; f(x) = x \land m_2$

6.4 CKKS

CKKS(Cheon-Kim-Kim-Song) представляет собой недетерминированный FHE для вещественных чисел. Его характерной особенностью является пакетирование(batching) - возможность обрабатывать сразу несколько чисел.

Пусть задан набор чисел $X = (x_1, \dots, x_l)$ .
Сначала он масштабируется $\Delta X = (\lfloor\Delta x_1\rfloor, \dots, \lfloor\Delta x_l\rfloor), \Delta \gg 1$ .
Затем кодируется полиномом $\hat{X} = Encode(\Delta X) \in R_Q$ .
Выбираются случайный полином $a \in R_Q$ и шум $e \in R_Q$ .
Полином сообщения шифруется по формуле аналогичной BFV.

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

7 Аппаратное ускорение FHE

Необходимость использовать недетерминированные шифры, а следовательно и bootstrapping, приводит к тому, что на данный момент большинство сервисов облачных вычислений не работают с FHE, из-за катастрофической разницы в сложности выполнения операций. Эта проблема может быть решена созданием аппаратных ускорителей, умеющих быстро делать все необходимые преобразования для заранее выбранного типа шифрования, что позволит по производительности приблизиться к вычислениям с открытым текстом.

Так, например, была представлена архитектура BASALISC [6] для облачных вычислений с шифром BGV и полнофункциональным bootstrap. Авторы получили ускорение $\sim 5 \cdot 10^3$ в сравнении с программной реализацией HElib.

Ещё одним интересным решением является REED [7]. У авторов статьи получилось ускорение $\sim 2.5 \cdot 10^3$ по сравнению с CPU(Intel X5690).

Всё это пока находится на стадии прототипов и исследований. На данный момент на рынке доступны решения на базе FPGA, но они имеют более скромные результаты.

8 Оценка перспектив

Популярность гомоморфных шифров в области облачных вычислений постепенно растёт, уже есть сервисы предоставляющие услуги хранения данных в зашифрованном виде с возможностью конфиденциальных вычислений, например, Hivenet, который использует GPU для работы с гомоморфными шифрами.

Ещё одним перспективным направлением является обработка биометрических данных с использованием FHE. Такие данные являются конфиденциальными, но их обработка требует больших вычислительных мощностей. Это идеальная задача для распределённых вычислений с использованием FHE.

Стоит также упомянуть задачу PPML(Privacy-Preserving Machine Learning) [8], которая состоит в обучении модели на зашифрованных данных и её последующем инференсе.

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

Список литературы

[1] Chiara Marcolla, Victor Sucasas, Member, IEEE, Marc Manzano, Riccardo Bassoli, Member, IEEE,Frank H.P. Fitzek, Senior Member, IEEE and Najwa Aaraj "Survey on Fully Homomorphic Encryption, Theory, and Applications" Proceedings of the IEEE 110(10), pp. 1572 - 1609, 2022

[2] Regev Oded "On lattices, learning with errors, random linear codes, and cryptography" Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 84-93, 2009

[3] Pascal Paillier "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes" in Advances in Cryptology — EUROCRYPT 99, Springer, pp. 223–238, 1999

[4] Andrey Kim, Yuriy Polyakov, Vincent Zucca "Revisiting Homomorphic Encryption Schemes for Finite Fields" Advances in Cryptology, pp. 608–639, 2021

[5] Ilaria Chillotti, Marc Joye, and Pascal Paillier "Programmable Bootstrapping Enables Efficient Homomorphic Inference of Deep Neural Networks" Cyber Security Cryptography and Machine Learning, pp. 1-19, 2021

[6] Robin Geelen, Michiel Van Beirendonck, Hilder V. L. Pereira1, Brian Huffman, Tynan McAuley, Ben Selfridge, Daniel Wagner, Georgios Dimou, Ingrid Verbauwhede, Frederik Vercauteren and David W. Archer "BASALISC: Programmable Hardware Accelerator for BGV Fully Homomorphic Encryption" IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 32-57, 2023

[7] Aikata Aikata, Ahmet Can Mert, Sunmin Kwon, Maxim Deryabin, Sujoy Sinha Roy "REED: Chiplet-based Accelerator for Fully Homomorphic Encryption" IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 163-208, 2025

[8] Luis Bernardo Pulido-Gaytan, Andrei Tchernykh, Jorge M. Cortes-Mendoza, Mikhail Babenko and Gleb Radchenko "A Survey on Privacy-Preserving Machine Learning with Fully Homomorphic Encryption" in High Performance Computing. CARLA 2020. Communications in Computer and Information Science, vol. 1327, pp. 115-129, 2021