查看原文
其他

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

The following article is from 隐私计算研习社 Author 沈华杰

同态加密是隐私计算的重要技术之一,利用该技术可以实现数据可用不可见。研习社将分上下两部分带来同态加密知识体系的整理,作者将现代的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等技术的发展与应用。

本周六下午,本文作者沈老师将在开放隐私计算社区城市见面会杭州站,分享同态加密知识体系,和大家一起讨论如何入门、学习难点,以及同态加密商业化程度、硬件加速最新进展问题,欢迎大家参与~

活动地点以及时间如下:

时间:2023年4月1日(本周六)下午14:00-17:00

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

惊喜:来现场,超多惊喜的社区周边精美大礼包等你噢!

扫码报名:

END
热门文章:




隐私计算头条周刊(3.20-3.26)


数据最高管理部门——国家数据局成立!


和文心一言聊一聊隐私计算,对比ChatGPT!


隐私计算领域大咖推荐,这些国内外导师值得关注


招标 | 近期隐私计算项目招标中标32(江阴智慧港口、广西壮族自治区公安厅、湛江市政务服务数据管理局、深圳信息职业技术学院等)

继续滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存