全同态加密知识体系整理(上)

同态加密是隐私计算的重要技术之一，利用该技术可以实现数据可用不可见。研习社将分上下两部分带来同态加密知识体系的整理，作者将现代的FHE技术视为两类，上半部分将重点介绍第一种——基于RLWE的层次同态加密（LHE），包括BGV，BFV和CKKS，这种方案一般来说支持多项式打包技术，可以一次性运算（加法乘法）多个数据，效率上较高，但LHE目前来说Bootstrapping开销比较大，一般来说只能当作支持有限次数的运算的同态加密方法使用。而在下半部分，我们将介绍第二类以FHEW和TFHE为代表的高效自举(Bootstrapping)技术。

1

基础知识

用粗体小写 a 来表示一个向量，小写a表示一个标量或者多项式，表示一个模和模多项式环， 表示向量或多项式的无穷范数，即中的最大项。表示一个随机分布（一般具体为高斯分布）。多项式环：: 定义为 , , 包含参数。: 。一般形式：例子：一般来说明文空间为或,密文空间为。
LWE问题： 有一个秘密向量，给定多组，其中是随机选取的向量，，通过 推出是困难的。RLWE问题： 有一个秘密向量，给定多组，其中是随机选取的多项式，，通过 推出是困难的。
2

基于RLEW的同态加密方案

BGV, BFV, CKKS

2.1 通用的格式

RLWE类型的同态加密（BGV，BFV，CKKS）密文的通用格式为, 有时候也写作，其中。

这里三个方案有一点小小的区别：

BGV的明文空间为，密文格式为，

BFV的明文空间为，密文格式为，

CKKS的明文空间为，密文格式为。

注意到BFV和CKKS中的定义是不一致的，BFV中作用是为了与BGV中的类似，是为了保证明文空间范围内解密的精确性。

而CKKS中是为了能够在中表示浮点数，以(k=10)的情况为例，可用1280表示。在应用中，可以取到60。

2.2 效率和功能方面

目前来说，我会把BGV和BFV放在一类，都是对于整数的同态加密方案。他们的计算能力（即噪声增长）和性能都差不多，在时，BGV效率会更优一些。但BFV的易用度要高于BGV，因为BGV的模数会不断变小，处理不同模数下密文之间的操作会比较麻烦，而BFV的模数是保持不变的。最小取2，最大取。

但由于BGV特殊的modulus switching机制，所以对于模数的选取有特殊要求，因此很多开源库没有实现BGV。都是将CKKS和BFV实现了，这两个协议可以共用一套参数(相同)。

对于CKKS来说，他的主要优势在于可以计算浮点数或者说复数 （但复数使用较少），效率方面与BGV和BFV相差不多，但有对于浮点数的计算有误差存在，不像BGV和BFV是精确的加密。

总结：三者的效率差不多。BGV和BFV是整数方案，精确。CKKS支持浮点数，不精确。

2.3 加解密流程

下面以CKKS举例说明一下RLWE类型密文的加密解密过程：

私钥加密流程： 

公开参数：多项式环，包含模数，多项式的阶，高斯分布。

输入：私钥，明文。 

输出：密文。有时写作，也有文章会写，表达的意思是一致的。

过程：

• 选取随机的多项式 ，以及。 

• 返回密文。

三个加密方案的区别在于第二步,或。目前私钥一般是从系数的多项式中选取，安全性与从中随机分布一致。BFV和BGV中要求，涉及到NTT编码。

公钥加密流程：

输入：公钥，明文。 

输出：密文 。 

过程： 

• 随机选取一个多项式，以及， 

• 返回密文

解密: 通用的解密公式为，以私钥的CKKS为例，（私钥）或者 （公钥）要求才可以正确的解密。这里的叫做噪声项。如果采用的是中心取模，即 表示正数，表示负数的情况下，额外要求：。这里三个方案有点区别：

• BGV计算后得到，通过模来实现去掉噪声，得到要求

• BFV计算后得到，其中，是通过乘然后四舍五入取整得到

，要求

• CKKS计算后得，其中，直接除来得到明文，要求才能解密。

注意到CKKS和BGV，BFV的主要区别在于，CKKS直接将噪声项作为了解密后明文的一部分，所以CKKS是无法解密得到精确解的。比如说，用CKKS加密，令，，那么解密后得到因此称CKKS是一个近似加密的，其中精度与相关。但精度越大，能做的乘法次数就越少。数量级关系差不多是次乘法。
2.4 同态性质加法两个密文

解密：

加法的噪声是原来的两倍。
明文密文加考虑密文

明文。有：

没有引入额外的噪声项，噪声是不变的。

明文密文乘

考虑密文

明文。有

解密

噪声大小变为倍。

乘法

考虑两个密文

乘法密文为

解密：

噪声大小是原来的平方，如何将变回将在噪声控制节中讲述。

密钥替换（重现性化）

思路：

有一个密文

要将其转换为由密钥加密的密文，步骤如下： 

输入：密文，转换密钥

相当于用加密的。

输出： 

正确性： 

但问题不能直接这么做，问题在于，噪声大小会直接超过，解密会失败。

正确算法：

因此一般KeySwitch都采用分解方法。分为和：

分别为： 

显然可以得到 

经过分解的转换算法： 

输入：密文，转换密钥 

输出： 

正确性： 

这个噪声项是远远小于没分解时的噪声项的。

例子：若，那么未分解时的噪声是，分解之后的噪声是。在最坏的情况下（即数组全是1），也可以将原本增大倍的噪声缩小为增大倍。

密钥替换的应用1：（重现性化） 

在做完一次乘法之后，乘法密文变为了 

可以通过密钥替换的方法，让，满足 

输入：密文 

替换密钥

为了书写简单，没有写成Decomp形式，可自行替换。

过程：

正确性：

注意，如果使用了比特分解，那么最后的噪声项为。

2.5 噪声控制

模数替换Modulus Switching（CKKS，BGV）

这里主要讲一下CKKS的MS过程，注意到，在CKKS方案中，做完了一次乘法之后，解密完的密文变为了： 

这里会取一个接近的数，然后将整个密文变为。

在模数替换之后，模数会减少个比特，同样噪声也会缩小倍，即减少个比特。 

模数替换在减少噪声和模数的同时会引入额外的噪声。 

模数替换后的解密得到的明文等于 

这里的的噪声的大小与初始噪声的大小相近。

因为是将scale factor 变回了，所以在CKKS中，也把这种方法叫做rescale

Scale Invariant（BFV）

在BFV方案中，乘法后得到的明文形式是： 

这里的是指与的差距，其中。

BFV是将密文变为。

没有改变模数而是直接改变密文，会引入额外的噪声。 

这里的噪声增长接近比特。

总结

• 如果不进行噪声控制，那么每次乘法之后噪声都会变成原本的平方，很容易大小就比要大，导致解密失败。

• 而使用MS方法可以将通过缩小模数的方法，来讲噪声控制在原来的水平，但一旦模数变为了比小，也会导致解密失败。

• BFV类型的噪声控制是通过在密文上乘法来做到的，好处是不用减少模数。

• BGV和CKKS的乘法能做的次数和BFV能做的次数是一致的。

• 在BGV和CKKS中，每次模数缩小的比特是或比特，

• 在BFV中，每次噪声增加的比特是比特。

• 模数越大，越小（BGV，BFV）/越小（CKKS），则能做的乘法次数越多。

2.6 Bootstrapping（通用方法）

最初由Gentry提出的Bootstrapping框架如上图所示。

1. 用一个白色的框来表示明文m。

2. 首先对明文进行了加密，用蓝色的框框住明文表示一个密文，密文旁边的条表示模数和噪声的关系，可以看到初始的噪声还是比较低的。

3. 在对密文执行了一系列操作之后，密文变为了，他的噪声达到了一个较高的水准，继续进行同态加法或乘法可能会导致解密失败。 

4. 这时候用某个同态加密方案来加密得到

5. 使用一个加密后的密钥，在与上面同态地执行操作。 

6. 最后可以得到

这里的噪声就与原来的噪声无关了，因为原本的噪声通过函数消除了。 

可以看到这个方法的缺点比较明显，就是开销特别大。而且本身算法比较复杂，会导致最后运算出来的密文带有较大的噪声，可能只能执行很少次数的同态乘法操作。

2.7 编码（SIMD, encoding）编码的目的是为了将多条数据打包成一个明文，对明文的一次操作可以对应多条数据的分别操作。在RLWE类型的同态加密中，明文是属于的，多项式包含了很多项，我们的需求是有效地利用起来这些项。我们对于中的密文会感觉比较直观一些，比如这样。在明文是时，其实也可以这样表示，比如令那也可以做到与相同的效果。但这样会噪声密文的浪费，因为多项式的系数有个，而这样只用到了个。需求是，将这个系数都用上，一次性能计算个明文。但是也不能直接将多个明文直接填入系数，那样就不满足同态乘法的性质了。举例，有一个明文数组与另一个数组，我们期望做他们之间的两两相加和两两相乘：得到与。如果直接按系数编码，。那么明显是不符合需求的。基于NTT&FFT
一种编码方式是使用点值多项式，比如一个明文数组 与另一个数组 相加和相乘。先不考虑 ，考虑在广义的多项式中。

带入四个点得

满足我们需要的编码需求。

一个很重要的观察就是，多项式的乘法可以对应到点值的两两相乘。

所以用点值形式来表示明文是Encoding的基本思路。

在上述的例子中，我们打包这个数组的方法是令

这样的方法是可行的，但效率不行。

基于FFT的编码(CKKS)

我们可以采用快速傅里叶变换（FFT）的方法来构造多项式。

取的解，这样的取法好处在于可以采用FFT的方式进行点值多项式到系数多项式之间的转换。

为什么FFT？因为这样的解是在单位元上面的一个对称的结构，可以通过二分的思想来加速运算，点值多项式到系数多项式之间的互相转换的复杂度是。

为什么是而不是，因为我们采用的多项式环是基于分圆多项式的商环，他的跟是即。

那照理来说，编码一个数组，就直接将

这样来构造一个多项式就行了。

但直接这样构造存在一个问题，就是出来的多项式的系数可能是复数。而我们加密所需要的多项式是一个整系数多项式，为了避免这一点，我们只用一半的点值，另一半存共轭，即：

数组，构造多项式满足

所以在说到CKKS的可利用槽的时候，一般说是，而不是。因为有一半的空间要用作存放共轭。

为了表示精度，这里一般是

基于NTT的编码(BGV, BFV)

对于BFV这样在中的多项式来说，使用编码时，我们取的解作为点值多项式的横坐标值。那么编码一个数组，就可以直接令

总结：

BFV：消息明文密文。 

CKKS：消息明文密文。

密钥替换的应用2：自同构（旋转，置换） 

对于编码之后的明文，我们可以在密文上执行一个旋转操作，使其变为。或者可以执行交换操作，使其变为。

注意点：这里例举的是CKKS密文，对应的，用到了个slot。

原理：对于密文来说，。

那么假如有一个galois自同构变换，那么。

可以直接对密文进行变换成为。这是一个用加密的密文。

那么就可以使用keyswitch操作，令

就可以将从由加密的密文变为了由加密的密文。

这里的可以是，比如

考虑的情况，编码。

旋转操作有什么用？

在一些涉及到矩阵乘法的应用中，比如大小的矩阵乘以大小的向量，如果，那么可以将矩阵编码进一个密文中，然后通过旋转的方式，执行矩阵乘向量。这种方法一般被叫做BSGS（小步大步法），在用FHE做机器学习训练或预测时非常常用。

φ除了表示旋转[1,2,3,4]变为[2,3,4,1]，还可以表示换位：[1,2,3,4]变为[3,4,1,2]。

作者简介：沈华杰，毕业于华东师范大学，目前任职电信翼支付的密码算法工程师，主要关注FHE，MPC，ZK等技术的发展与应用。

本文作者沈老师将在开放隐私计算社区城市见面会杭州站分享FHE知识体系，欢迎大家参与~

活动地点以及时间如下：

时间：2023年4月1日（本周六）下午14：00-17：00

地点：浙江省杭州市滨江区西兴街道联慧街188号安恒大厦

报名方式：扫码报名

END

往期推荐

1.基于密码的数据安全防护体系研究
2.联邦学习安全聚合：基于安全多方计算的经典方案3.椭圆曲线密码在多方安全计算中的应用4.隐私求交| Simple, Fast Malicious Multiparty Private Set Intersection