同态加密:CKKS ⽅案简介及⼀个python 实现:TENSEAL (不定期更新)0x01 同态加密的CKKS ⽅案简介
CKKS是2017年提出的同态加密⽅案。它⽀持浮点向量在密⽂空间的加减乘运算并保持同态,但是只⽀持有限次乘法的运算。同态加密极简介绍
举个例⼦:
实数域⾥有加法和乘法。多项式域⾥⾯有多项式加法和多项式乘法。我们把实数域中的数或者向量映射到多项式域(加密),在多项式域⾥做⼀些多项式加法和多项式乘法的运算之后,再把多项式映射回实数域(解密),得到的结果和实数域⾥做对应的加法和乘法的结果相同或者相似。这种在私密领域(例如多项式域)做确保结果⼀致性的计算技术就叫同态加密。
LWE 问题的极简介绍
格(lattice)
在线性空间中给定⼀组线性⽆关的向量,其整数线性组合⽣成的集合称为格。
关于格的详细介绍,不妨移步。
LWE问题
我们有了若⼲的对,其中为整数向量,为整数(均在mod Q意义下)。现在需要⼀个线性函数,使得。由Risez表⽰定理,总是存在⼀个和a形状相同的,使得,其中是和的内积。在CKKS中,这⾥的线性函数就是和私钥做内积,私钥也是整数向量(mod Q),即可以理解为求解线性⽅程组:
但是,在LWE(learning with error)问题中,我们加⼊了⼀些误差,此即:
其中,内积就表⽰待定的(因为f是线性的)。为整数,是引⼊的误差。
如果没有误差的话,⾼斯消去法可以把解出来,但是误差的引⼊和对中元素整数性的要求就使得解会特别病态甚⾄搞不出来符合要求的解。
上⾯所说的LWE问题是search-LWE问题,即已知寻。
还有⼀种Decision-LWE问题,说的是判断到底是随机⽣成的整数向量还是由⽣成的东西。
RLWE问题
雪崩被埋能爬出来吗和LWE问题类似,只不过这⾥的 都是整数多项式,⽽且对应地LWE⾥的内积换成了多项式的乘法。可以证明,这个问题的求解也是困难的。
CKKS 操作步骤
这⾥就直接贴图了,会附上⼀些⽂字说明帮助理解。
(a ,b )a b f f (a )≈b s f (a )=(a ,s )(a ,s )a s a s s (a ,s )=i b i
(a ,s )+i e =i b i
(∗,s )f (∗)e s s a ,b s b (a ,s )+e a ,b ,s
上图是CKKS的⼀个⼤概流程。先对消息(向量)进⾏编码,然后再加密,在密⽂空间进⾏⼀些运算后再解密,最后解码成运算后的消息(向量)。注意,这⾥的编码指的是将复数向量映射成为多项式,是为了⽅便下⾯进⼀步的加密,
上图是编解码的⽅法。
编码:Message -> m(X)
是⼀个 维的复向量。在拿到⼀个复向量之后,对它取⼀下共轭并且将原向量和共轭拼接在⼀起,得到増⼴的。
⽐如,我们拿到了⼀个复向量。按照上⾯所说的做法,我们将它増⼴为:Message 2n Message ∈C 2n
Message ∈′C n (1+4i ,5−2i )
考虑复数域内多项式,它有个复根,记这些复根组成的向量为 ,并且前个根和后个根也是共轭的。
下⾯,我们求⼀个整数系数的插值多项式(⽤⽜顿插值、拉格朗⽇插值、快速傅⾥叶变换啥的都可以),使得。即把 的复数根作为⾃变量丢到 ⾥⾯去,使得输出的值是的对应分量。
由于共轭性质,插值出来的 的系数都是实数。但是,CKKS最后要对整数进⾏操作,因此需要对多项式系数进⾏取整。如果直接对 系数取整,误差会⽐较⼤。因此在这⾥我们引⼊放⼤因⼦ ,将Message的数值放⼤,得到之后再进⾏取整。这样的话,可以尽可能保留⼩数的位数,提⾼加密的精度。但是引⼊了放⼤这样⼀个操作之后,多项式系数就不可避免地变⼤了很多。如果再做很多乘法,那就不可避免地会出现溢出的情形。它的应对⽅法可以参考下⾯的重缩放部分。
即为对消息编码的结果。
对编码结果做存储时,我们只需要存储 的系数即可。
按理说,这⾥的n需要是2的幂,但是由于这⾥我们只涉及编码解码操作,所以没有特别地提及这个事情,因为这⾥n/2只要是整数的话,不影响后⾯加解密的运算。只有在旋转和bootstrap下需要使⽤到n是2的幂这个条件,因为此时的分圆多项式的形状⽐较好,是的形式。
解码:Message <- m(X)
把上述步骤倒过来就⾏了。我们已知了 ,接下来把 带进去就完事了。
最后别忘了除以 就⾏。
加密:m(X) -> (c0(X), c1(X))
这⾥,我们取私钥,公钥,其中 和 是向量,是⼀个随机数, 是⼀个数。(这⾥就由RLWE问题确保了⼀件事:仅使⽤公钥的话很难解出私钥)
则密⽂,其中是随机整数,是随机的多项式(也可以理解为向量)。
涉及的所有乘法都相当于多项式乘法。
解密:m(X) <- (c0(X), c1(X))
(1+4i ,5−2i ,1−4i ,5+2i )
X +n 1n ξi ξ2n 2n m (X )m (ξ)≈Δ×Message i ′X +n 1=0m Message ′m m Δm =m ⋅Δm m X +n 1m ξΔ(1,s )(b =−a ⋅s +e ,a )s a e b (c ,c )=01r (b ,a )+(m +e ,e )=12(rb +m +e ,ra +1e )2r e ,e 12
计算即可,其结果约等于。
过程如下(这个式⼦最后的符号好像有点问题,我没有改,可以结合评论区看⼀看,感谢评论区⽼哥指正):
加法(明⽂向量按元素相加)
两个密⽂向量直接对应相加。
明⽂乘密⽂(明⽂多项式和密⽂多项式的乘法)
其本质就是直接把明⽂和密⽂中的逐个做多项式乘法,得到的就是新的密⽂。但是,这⾥的乘法会不
可避免地导致乘积多项式的次数增加,进⽽需要更多的空间来存储。这⾥就需要⽤下⽂所说的重线性化来将乘积多项式控制到合适的多项式次数上。
密⽂乘密⽂(密⽂多项式的乘法)
其本质就是重线性化
我们需要注意,明⽂和密⽂向量本质上是⼀个多项式,向量的内容是多项式的系数。多项式相乘完毕之后,其次数必然会升⾼。
⽐如,现在有两个密⽂分别是 和 ,如果直接做多项式相乘的话,得到的结果是 。因此,密⽂空间的乘法会导致密⽂向量对应的密⽂多项式“次数”变⼤(但是如果把它对应的多项式进⾏解码,忽略误差的话,得到的Message还是同⼀个Message)。但是,从明⽂空间上看,上述动作还只是两个向量的逐元素相乘,我们希望进⾏在密⽂空间中做乘法之后密⽂向量对应的多项式“次数”保持不变,即,没有 的平⽅项。
解决⽅法是这样的:我们启⽤⼀个重线性化秘钥。我们将⽰例记为:update后面接什么
其中 都是可以⽤密⽂乘积计算出来的。
输出的密⽂结果就是,其中 是⼀个⽤于重缩放的特殊模数。
理由如下:重缩放
上述推演过程中还是有不严谨地⽅的。其中⼀个重要的地⽅便是取模。
常理来说,我们对上⾯每⼀步运算都需要取模的,只是正常计算的过程中,我们算的数(包括编码、加密、加法、乘法)都⽐较⼩,即使是放⼤因⼦也⽐取模的模数⼩很多,所以取模⼀般是取个寂寞。因此我在上⾯就没写这个事⼉。
但是当我们做乘法做多了之后,放⼤因⼦就多起来了,并且在最坏情况下放⼤因⼦数将呈指数增长。结果就有可能溢出模数了,溢出之后就⽩算了。
PS:放⼤因⼦增多的情况只出现于密⽂相乘的情形中。
CKKS的解决办法是使⽤分层乘法机制。为此,CKKS设计了⼀个有限乘法全同态加密的机制,并且引⼊了⼀个模数链 。这⾥的 是和 “差不多”⼤⼩的素数, 称为乘法深度,可以理解为最多能做多少次乘法。刚加密的密⽂的模数是 ,以后每做⼀次密⽂相乘, 都会变多,这⾥就可以对系数除以⼀个 (也相当于对模数除以 )来抵消掉这个增加的 ,这样就可以确保密⽂数据中⾃始⾄终仅有⼀个,但是相应地会导致乘法深度的降低(因为做乘法会导致模数变⼩,因为对模数除以了,当模数变⼩到⼀定程度就可能溢出)。
c +0c s 1m c +0c s =1rb +m +e +1ra ⋅s +e s =2m +e +1e s −2er
m ×(c +1c s )=2mc +1mc s
2m c ,c 12(c m ,c m )12(c +11c s )×12(c +21c s )=22c c +1121(c c +2112c c )s +1122c c s 12222
c +0c s 1c +2c s 3c c +02(c c +03c c )s +12c c s 132(c +0c s )∗1(c +2c s )=3(
d +0d s )1s evk =(b ,a )=′′(−a ⋅s +′
e +′bs ,a )2′c c +02(c c +03c c )s +12c c s 132d +0d s +1d s 22
d ,d ,d 012(c ,c )=1′2′
(d ,d )+01P ⋅d ⋅evk −12P P d (b ,a )⋅(1,s )=−12′′P ⋅d ⋅b +−12′P ⋅d ⋅a ⋅s =−12′d s +22P d e ≈−12′d s 22
ΔQ =q ⋅p 0L p ΔL Q Δp p ΔΔp
writeas邵李程秀旋转(Rotation)
这个操作在SEAL库中实现,但是在TenSEAL库中似乎没有实现。tenseal库的作者表⽰,他们把旋转操作集成到了乘法⾥⾯,没有直接提供旋转操作的api。
它会⽤到⼀个Galois秘钥,⼲的事情如下:
[1,2,3,4,5] -> [5,1,2,3,4] -> [4,5,1,2,3]
大学生学c语言用什么书这⾥应该是要⽤到Galois理论相关的东西。我近世代数课到这⼀块⽼师讲得太快了所以划⽔过去的…过⼏天学⼀学再补吧…
经过实操来看,这个Galois密钥⾮常占⽤空间。
当然,通过线性代数中的矩阵乘法其实也可以实现旋转操作,其⽅法⽆⾮就是再⽣成⼀个明⽂的变换矩阵,以⼀个乘法深度为代价(因为要做矩阵乘法)做相应的变换就⾏了…需要注意,正常的旋转操作不会消耗乘法深度。
Bootstrapping
假如我们有⼀个即将耗尽乘法深度的密⽂,我们可以⽤Bootstrapping来让它重新“焕发⽣机”,将它的乘法深度恢复到原始密⽂的深度。
极简python快速入门教程这个事情的计算开销⽐较⼤。⽬前有⼀些库⽀持Bootstrapping操作,还有⼀些快速的bootstrapping⽅法。但是⽬前SEAL和TenSEAL库都不⽀持Bootstrapping操作。
开发软件流程当然了,如果像我⼀样懒得搞这些花⾥胡哨的玩应的话,不妨直接把需要做bootstrap的向量发送给私钥持有⽅,让它给你解密后再加密就完事了。
杂项
矩阵的乘法是可以实现的。可以参见ICLR2021中TenSEAL库的⽂章。还有很多专门研究如何在同态加密下做矩阵乘法的⽂章。
0x02 同态加密库PySyft和TenSEAL
⽹上常见的同态加密库是SEAL库,但是是⽤C++编写的。
在把玩SEAL库的过程中,本⼈倒在了第⼀步:编译。
遂寻替代品。
到⼀个,它将SEAL⽤python进⾏包装,编程⽐较⽅便。这个库已经发表在了上。
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论