同态加密：CKKS方案详解及一个python实现:TenSEAL

用人话介绍的CKKS同态加密方案。

PenguinLeee

37287人浏览 · 2021-07-16 19:36:38

PenguinLeee · 2021-07-16 19:36:38 发布

部分资料来自于HEAAN作者的个人主页：https://yongsoosong.github.io/files/slides/intro_to_CKKS.pdf

2024年5月30日来挖坟，我之前调研了一下用CKKS方案做矩阵/张量加法、乘法、转置的方法，发现没有像TenSEAL实现这么丝滑的，基本都需要做一些麻烦的转换。结合TenSEAL张量的计算、存储开销，我高度怀疑TenSEAL直接把张量里每个数单独地进行了加密。

0x00 引流

本文是CKKS方案的简介，在文章中不会涉及太多的数学。BGV、BFV方案和此方案在原理上存在一定的相似性。涉及CKKS更深层次的原理，请参考本专栏的其他博客。

0x01 同态加密的CKKS方案简介

CKKS是2017年提出的同态加密方案。它支持浮点向量在密文空间的加减乘运算并保持同态，但是只支持有限次乘法的运算。

同态加密极简介绍

举个例子：
实数域里有加法和乘法。多项式域里面有多项式加法和多项式乘法。我们把实数域中的数或者向量映射到多项式域（加密），在多项式域里做一些多项式加法和多项式乘法的运算之后，再把多项式映射回实数域（解密），得到的结果和实数域里做对应的加法和乘法的结果相同或者相似。这种在私密领域（例如多项式域）做确保结果一致性的计算技术就叫同态加密。

LWE问题的极简介绍

格(lattice)

在线性空间中给定一组线性无关的向量，其整数线性组合生成的集合称为格。

关于格的详细介绍，不妨移步这里。

LWE问题
我们有了若干的 $(a, b)$ 对，其中 $a$ 为整数向量， $b$ 为整数。现在需要找一个线性函数 $f$ ，使得 $\approx b$ 。由Risez表示定理，总是存在一个和a形状相同的 $s$ ，使得 $f (a) = (a, s)$ ，其中 $(a, s)$ 是 $a$ 和 $s$ 的内积。在CKKS中，这里的线性函数就是 $a$ 和私钥 $s$ 做内积，私钥 $s$ 也是整数向量，即可以理解为求解线性方程组：
$a_i, s) = b_i$
但是，在LWE(learning with error)问题中，我们加入了一些误差，此即：
$a_i, s) + e_i = b_i$
其中，内积 $(*, s)$ 就表示待定的 $f (*)$ （因为f是线性的）。 $e$ 为整数，是引入的误差。

如果没有误差的话，高斯消去法可以把 $s$ 解出来，但是误差的引入和对 $s$ 中元素整数性的要求就使得解会特别病态甚至搞不出来符合要求的解。

上面所说的LWE问题是search-LWE问题，即已知 $a, b$ 寻找 $s$ 。
还有一种Decision-LWE问题，说的是判断 $b$ 到底是随机生成的整数还是由 $(a, s) + e$ 生成的东西。

RLWE问题
和LWE问题类似，只不过这里的 $a, b, s$ 都是整数多项式，而且对应地LWE里的内积换成了多项式的乘法。可以证明，这个问题的求解也是困难的。

CKKS操作步骤

这里就直接贴图了，会附上一些文字说明帮助理解。

在这里插入图片描述

上图是CKKS的一个大概流程。先对消息（向量）进行编码，然后再加密，在密文空间进行一些运算后再解密，最后解码成运算后的消息（向量）。
注意，这里的编码指的是将复数向量映射成为多项式，是为了方便下面进一步的加密，

在这里插入图片描述
上图是编解码的方法。

一些数论背景

首先，给出一些记号。 $\mathbb Z_M$ 是模 $M$ 剩余类， $\mathbb Z_M^*$ 是 $\mathbb Z_M$ 里所有带有乘法逆的元素组成的集合。

$\phi(n) = \#\{k: gcd(n, k) = 1\}$ 是欧拉函数，其值为所有小于 $n$ 且和 $n$ 互素的正数的计数数目。

一个例子是 $M = 8$ ， $\phi(M) = 4$ ，因为可以考虑集合 ${1, 3, 5, 7\}$ ，其值为所有小于 8 且和 8 互素的正数的计数数目。

考虑 $\omega := e^{2\pi i/m} \in \mathbb C$ 为原根， $m = M /2$ ， $\Phi_M(X) := \prod_{j \in \mathbb Z_M^*}(X - \omega^j) \in \mathbb C[X]$ 称为 $m$ 次分圆多项式（这里是凭记忆写的，不保证正确性，但是相关的定义可以在分圆多项式的各种note中查到）。

对于 $M > 4$ ，我们有 $\phi(M) = M/2$ 并且分圆多项式 $\Phi_M(X) = X^N + 1$ ，此即在CKKS方案中，要求 $M$ 是2的整数次幂。此时， $\phi(M) = M/2$ ，所有和 $M$ 互素的数有且仅有小于等于 $M$ 的奇数，一共 $M /2$ 个。此时的分圆多项式结构是相当规整的，因为：

对应的分圆多项式的根是两两共轭的，这确保了编码步骤（下文所述）中插值多项式系数为实数的性质。
分圆多项式 $\Phi_M(X)$ 的根构成乘法群。取原根 $\omega$ ，取 $1,5,5^2,5^3...$ 次方构成的集合记为 $\{\omega_+\}$ ，取 $1, -5, -5^2, -5^3...$ 次方构成的集合记为 $\{\omega_-\}$ 。有 $\{\omega_+\}$ 、 $\{\omega_-\}$ 中的元素个数相等、互不相同、互为共轭。这个性质确保了后续的旋转操作。

编码：Message -> m(X)

下面涉及的是将一个向量写成多项式的形式。

$M ess a g e$ 是一个 $\frac{n}{2}$ 维的复向量。在拿到一个复向量 $\in C^{\frac{n}{2}}$ 之后，对它取一下共轭并且将原向量和共轭拼接在一起，得到増广的 $\in C^n$ 。

比如，我们拿到了一个复向量 $(1 + 4 i, 5 - 2 i)$ 。按照上面所说的做法，我们将它増广为：

$(1 + 4 i, 5 - 2 i, 5 + 2 i, 1 - 4 i)$

考虑复数域内多项式 $X^n+1$ ，它有 $n$ 个复根 $\xi_i$ ，记这些复根组成的向量为 $\xi$ ，并且前 $\frac{n}{2}$ 个根和后 $\frac{n}{2}$ 个根也是共轭的。

下面，我们求一个整数系数的插值多项式 $m (X)$ （用牛顿插值、拉格朗日插值、快速傅里叶变换啥的都可以），使得 $m(\xi) \approx \Delta \times Message'_i$ 。即把 $X^n + 1 = 0$ 的复数根作为自变量丢到 $m$ 里面去，使得输出的值是 $M ess a g e^{'}$ 的对应分量。

由于共轭性质，插值出来的多项式 $m$ 的系数都是实数，这个性质对于理解CKKS方案是很重要的。但是，CKKS最后要对整数进行操作，因此需要对多项式系数进行取整。如果直接对 $m$ 系数取整，误差会比较大。因此在这里我们引入放大因子 $\Delta$ ，将Message的数值放大，得到 $\Delta$ 之后再进行取整。这样的话，可以尽可能保留小数的位数，提高加密的精度。但是引入了放大这样一个操作之后，多项式系数就不可避免地变大了很多。如果再做很多乘法，那就不可避免地会出现溢出的情形。它的应对方法可以参考下面的重缩放部分。

$m$ 即为对消息编码的结果。

对编码结果做存储时，我们只需要存储 $m$ 的系数即可。

按理说，这里的n需要是2的幂，但是由于这里我们只涉及编码解码操作，所以没有特别地提及这个事情，因为这里n/2只要是整数的话，不影响后面加解密的运算。只有在旋转和bootstrap下需要使用到n是2的幂这个条件，因为此时的分圆多项式的形状比较好，是 $X^n+1$ 的形式。

解码：Message <- m(X)

把上述步骤倒过来就行了。我们已知了 $m$ ，接下来把 $\xi$ 带进去就完事了。

最后别忘了除以 $\Delta$ 就行。

加密：m(X) -> (c0(X), c1(X))
在这里插入图片描述
这里，我们取私钥 $(1, s)$ ，公钥 $(b = - a \cdot s + e, a)$ ，其中 $s$ 和 $a$ 是向量， $e$ 是一个随机数， $b$ 是一个数。（这里就由RLWE问题确保了一件事：仅使用公钥的话很难解出私钥）
则密文 $c_0, c_1) = r(b, a) + (m + e_1, e_2) = (rb + m + e_1, ra + e_2)$ ，其中 $r$ 是随机整数， $e_1, e_2$ 是随机的多项式（也可以理解为向量）。

涉及的所有乘法都相当于多项式乘法。

解密：m(X) <- (c0(X), c1(X))

计算 $c_0 + c_1s$ 即可，其结果约等于 $m$ 。

过程如下（这个式子最后的符号好像有点问题，我没有改，可以结合评论区看一看，感谢评论区老哥指正）：
$c_0 + c_1s = rb + m + e_1 + ra·s + e_2s = m + e_1 + e_2s - er$

加法（明文向量按元素相加）

两个密文向量直接对应相加。

明文乘密文（明文多项式和密文多项式的乘法）
其本质就是 $\times (c_1+ c_2s) = mc_1 + mc_2s$
直接把明文 $m$ 和密文中的 $c_1, c_2$ 逐个做多项式乘法，得到的 $c_1m, c_2m)$ 就是新的密文。但是，这里的乘法会不可避免地导致乘积多项式的次数增加，进而需要更多的空间来存储。这里就需要用下文所说的重线性化来将乘积多项式控制到合适的多项式次数上。

密文乘密文（密文多项式的乘法）
其本质就是 $(c_{11}+ c_{12}s) \times (c_{21}+ c_{22}s) = c_{11}c_{21} + (c_{21}c_{12}+c_{11}c_{22})s + c_{12}c_{22}s^2$

重线性化
我们需要注意，明文和密文向量本质上是一个多项式，向量的内容是多项式的系数。多项式相乘完毕之后，其次数必然会升高。

比如，现在有两个密文分别是 $c_0 + c_1s$ 和 $c_2 + c_3s$ ，如果直接做多项式相乘的话，得到的结果是 $c_0c_2 + (c_0c_3 + c_1c_2)s + c_1c_3s^2$ 。

因此，密文空间的乘法会导致密文向量对应的密文多项式“次数”变大（但是如果把它对应的多项式进行解码，忽略误差的话，得到的Message还是同一个Message）。但是，从明文空间上看，上述动作还只是两个向量的逐元素相乘，我们希望进行在密文空间中做乘法之后密文向量对应的多项式“次数”保持不变，即 $c_0 +c_1s) * (c_2 + c_3s) = (d_0 + d_1s)$ ，没有 $s$ 的平方项。

解决方法是这样的：我们启用一个重线性化秘钥 $evk = (b', a') = (-a'·s + e' + bs^2, a')$ 。我们将示例 $c_0c_2 + (c_0c_3 + c_1c_2)s + c_1c_3s^2$ 记为：

$d_0 + d_1s + d_2 s^2$

其中 $d_0, d_1, d_2$ 都是可以用密文乘积计算出来的。

输出的密文结果就是 $c'_1, c'_2) = (d_0, d_1) + P^{-1}·d_2·evk$ ，其中 $P$ 是一个用于重缩放的特殊模数。

理由如下：

$P^{-1}d_2(b', a')·(1, s) = P^{-1}·d_2·b' + P^{-1}·d_2·a' ·s = d_2s^2 + P^{-1}d_2e' \approx d_2s^2$

重缩放

上述推演过程中还是有不严谨地方的。其中一个重要的地方便是取模。

常理来说，我们对上面每一步运算都需要取模的，只是正常计算的过程中，我们算的数（包括编码、加密、加法、乘法）都比较小，即使是放大因子 $\Delta$ 也比取模的模数小很多，所以取模一般是取个寂寞。因此我在上面就没写这个事儿。

但是当我们做乘法做多了之后，放大因子就多起来了，并且在最坏情况下放大因子数将呈指数增长。结果就有可能溢出模数了，溢出之后就白算了。

PS：放大因子增多的情况只出现于密文相乘的情形中。

CKKS的解决办法是使用分层乘法机制。为此，CKKS设计了一个有限乘法全同态加密的机制，并且引入了一个模数链 $Q = q_0 · p^L$ 。这里的 $p$ 是和 $\Delta$ “差不多”大小的素数， $L$ 称为乘法深度，可以理解为最多能做多少次乘法。刚加密的密文的模数是 $Q$ ，以后每做一次密文相乘， $\Delta$ 都会变多，这里就可以对系数除以一个 $p$ （也相当于对模数除以 $p$ ）来抵消掉这个增加的 $\Delta$ ，这样就可以确保密文数据中自始至终仅有一个 $\Delta$ ，但是相应地会导致乘法深度的降低（因为做乘法会导致模数变小，因为对模数除以了 $p$ ，当模数变小到一定程度就可能溢出）。

在这里插入图片描述
旋转(Rotation)

这个操作在SEAL库中实现，但是在TenSEAL库中似乎没有实现。tenseal库的作者表示，他们把旋转操作集成到了乘法里面，没有直接提供旋转操作的api。

它会用到一个Galois秘钥，干的事情如下：

[1,2,3,4,5,0,0,0] -> [0,0,1,2,3,4,5,0] -> [4,5,0,0,0,1,2,3]

本质上是在编码操作中对根的排列做了一些变动，使得用起来更顺手。具体原理可以参考我的这篇博客。欢迎各位dalao纠错。

Bootstrapping

假如我们有一个即将耗尽乘法深度的密文，我们可以用Bootstrapping来让它重新“焕发生机”，将它的乘法深度恢复到原始密文的深度。

这个事情的计算开销比较大。目前有一些库支持Bootstrapping操作，还有一些快速的bootstrapping方法。但是目前SEAL和TenSEAL库都不支持Bootstrapping操作。

当然了，如果像我一样懒得搞这些花里胡哨的玩应的话，不妨直接把需要做bootstrap的向量发送给私钥持有方，让它给你解密后再加密就完事了。

Bootstrapping操作的原理可以参考这篇博客，同样欢迎各位dalao纠错。

杂项

矩阵的乘法是可以实现的。可以参见ICLR2021中TenSEAL库的文章。还有很多专门研究如何在同态加密下做矩阵乘法的文章。

后来，我没有直接用同态加密做矩阵的乘法，更多用到了矩阵乘向量，而且TenSEAL中对于矩阵的实现十分复杂，并且开销比较大，所以这里暂时放上一个比较简单的矩阵乘向量的实现。

0x02 压缩版本的简介

从一篇CKKS的应用论文中截取下来的东西，供大家参考：

在这里插入图片描述

0x03 同态加密库PySyft和TenSEAL

网上常见的同态加密库是SEAL库，但是是用C++编写的。

（还有一些正在用的过一阵子再补）

在把玩SEAL库的过程中，本人倒在了第一步：编译。

遂寻找替代品。

找到一个TenSEAL，它将SEAL用python进行包装，编程比较方便。这个库已经发表在了ICLR2021上。

也找到了一些FHE（全同态加密）的一些实现。

PySyft似乎包含了TenSEAL，留待日后品鉴。

（2021年7月23日更新，确实包含了TenSEAL，在 syft.frameworks.tenseal 中）
（我鸽了，因为暂时用不到PySyft）

（后来安了个ubuntu就发现各种同态加密库都可以把玩，编译也不再是啥大问题，遂休了TenSEAL。但是不得不说，TenSEAL库对于新手是十分友好的）

熟悉TenSEAL

TenSEAL是一个具有Python接口的C++库。

这个库有两个好处。

一个是安装比SEAL省心，直接 pip install tenseal 完事了。

一个是不需要过多地考虑CKKS的实现细节（比如矩阵乘法的底层细节），直接梭哈就完事了。

TenSEALContext

这是本人对TenSEAL的一些API做的一个封装。

这个Context上下文相当于对CKKS的秘钥等参数做了一个封装。我们只需要在编码、加密、加、乘、解密的时候把上下文作为参数扔进去就完事了。

import tenseal as ts
import numpy as np

def gencontext():
    context = ts.context(ts.SCHEME_TYPE.CKKS, 8192, coeff_mod_bit_sizes=[22 ,21, 21, 21, 21, 21, 21, 21, 21, 21])
    context.global_scale = pow(2, 21)
    context.generate_galois_keys()
    return context

def encrypt(context, np_tensor):
    return ts.ckks_tensor(context, np_tensor)

def decrypt(enc_tensor):
    return np.array(enc_tensor.decrypt().tolist())

def bootstrap(context, tensor):
    # To refresh a tensor with exhausted depth. 
    # Here, bootstrap = enc(dec())
    tmp = decrypt(tensor)
    return encrypt(context, tmp)

if __name__ == "__main__":

    a = np.array([[1.,2.,3.,4.], [1.,2.,5.,4.]])
    context = gencontext()
    enc_a = encrypt(context, a)
    enc_at = encrypt(context, a.T)
    enc_b = encrypt(context, a)
    res = enc_a + enc_b
    # res = enc_a - enc_b
    # res = enc_a * enc_b
    # res = enc_a @ enc_at
    print(decrypt(res))

加密和解密

context = context()

message = [60, 66, 73, 81, 90]

plain_vector = ts.plain_tensor(message)

encrypted_vector = ts.ckks_vector(context, plain_vector)

print(encrypted_vector.decrypt().tolist()) # tolist是用来将多项式m(X)解码成张量的

# 加法和乘法直接使用+, *, @ 即可
m1 = [1, 2, 3]
m2 = [4, 5, 6]
p1, p2 = ts.plain_tensor(m1), ts.plain_tensor(m2)
e1, e2 = ts.ckks_vector(context, p1), ts.ckks_vector(context, p2)
e1 + e2
e1 * e2
e1 @ e2

0x04 实现细节

理论上CKKS的加解密是这么操作的，但是实际上还有很多为了性能做出的优化。

向量的编码

这里我们要谈一下向量编码的部分，就是这里做的事情：

在这里插入图片描述

前面说过，这里我们根据多项式在每个点的值来确定多项式本身的样子（就是确定多项式的系数）。这个方法其实有很多，比如数值计算方法里会讲到的那几种插值。

但是，在CKKS中，并不会真正地存储一个多项式。而是存储若干的向量对。向量对的内容是：分圆多项式 $X^N + 1$ 的所有根和拼接了共轭部分的原向量。比如，复向量 $(1 + 4 i, 5 - 2 i)$ 。增广后的结果是 $(1 + 4 i, 5 - 2 i, 1 - 4 i, 5 + 2 i)$ 。存储在计算机中的结果就是 $X^4+1=0$ 的四个根（前两个和后两个共轭）以及 $(1 + 4 i, 5 - 2 i, 1 - 4 i, 5 + 2 i)$ 捏在一块构成的向量对。

为什么这么做呢，因为如果真的存储了多项式（在计算机里面是存储多项式的各项系数），那么做乘法会是一件十分麻烦的事情。我记得数据结构中有一道经典的题目，就是用链表实现多项式乘法。感兴趣的可以试着实现一下体验体验难度。由于涉及大量的同类项合并，所以算起来十分难受。此外在CKKS中，做了多项式乘法还意味着要做多项式的重线性化，反正我是不想动手实现的。

于是密文乘法就直接乘对应的增广向量就完事了，连重线性化都不需要做。有一个定理保证了上面这些事的正确性：n-1次多项式最多有n个根。