全球数字财富领导者

初探全同态加密之三:构建GSW全同态加密系统

2023-10-10 15:40:21
金色财经
金色财经
关注
0
0
获赞
粉丝
喜欢 0 0收藏举报
— 分享 —
摘要:这一期,我们真正开始实战最后的boss——开始构造全同态加密系统。

作者:Steven Yue,原刊于作者知乎

上一期的文章中,我们一起了解了格密码学到底是什么,随后我们学习了LWE问题的构造。最后,我们把所学的内容组合起来,构成了格密码学中最经典的Regev加密算法。(详情点击《初探全同态加密:FHE的定义与历史回顾》)

希望看到这里,大家已经对上期讲到的内容已经有一个深刻的认知了。这一期,我们就可以真正开始实战最后的boss——开始构造全同态加密系统。

上期回顾

在开始之前,为了便于大家能够更好理解这期会描述的FHE系统,我们在此快速的复习一下之前两期文章讲到的比较关键的知识点。

LWE问题

上期文章中较为重点的内容就是LWE问题了。可以说正确的理解了LWE,格密码学和FHE问题就已经搞定了一大半了。

TxfZxm6nUEKTg6uhS0UcxyADRmwQDxAUqQAEwwBz.png
Sg6C1Pxh7lNc2wfrPPIZWvHol2sFFWBS0WUeQQAC.png
LxLWdS7fGcO7cmCIvyQnYP6NGwyXaKRtheKDrIW8.png
l5SpRz7t3C3K0a3NV7amlaup1h6LkFG1MoRk8fKO.png
bXTK8FRCwyR1PQRCxJmfRWLEyXC4COAQ7Gl2VyVL.png
UiEdZkHjj3a6Y35wHlHX4Uw2z8uNjuu6OsDmzlxg.png

全同态加密体系

最后,我们一起来回顾一下上上期讲到的,一个完整的全同态加密(FHE)体系的构造。

1rgyon8mHfUCaT7dsIYnP1TZqIPhJ7ILIqE0QiUD.png
7pNGXFcRjv2WW7fb5FWpwJni2VWNcOfDYhuIiv5W.png
YfOHdp67hoUOz2unD0RPF5xldsHt3kJH0DWCo3NV.png

FHE的四个阶段

我们在第一期的文章中,还学习了构成FHE系统的四个不同阶段:

  1. 部分同态(Partially Homomorphic Encryption):在这一阶段下,我们可以运算的功能F只能够要么由加法/线性组合,要么由乘法构成。常见的例子有RSA(乘法同态)以及ElGamal(加法同态)。

  2. 近似同态(Somewhat Homomorphic Encryption):这一阶段的算法拥有不完整的同态属性,比如拥有Pairing配对的ElGamal循环群,具有完整的加法同态属性,但是只有非常薄弱的乘法同态属性。

  3. 有限级数全同态(Leveled Fully Homomorphic Encryption):这一阶段的算法可以同态运算任意形式的功能F,但所转换成的电路的复杂度不能超过上限L,不然就会噪音太大丢失信息。

  4. 全同态(Fully Homomorphic Encryption):最后的阶段就是我们想要得到的FHE了。在这一阶段我们可以计算任意复杂度的功能F, 并且噪音可以被完美的控制在可控范围内。

我们之前还提到了,通过Bootstrapping的方式,可以有效的将一个有限级数全同态(LFHE)的系统转换为一个全同态(FHE)的系统。Bootstrapping这一概念是FHE界的开山鼻祖Craig Gentry在09年的PhD毕业论文中指出的。我们这次要讲到的GSW系统,就是一个FLHE系统,随后通过Bootstrapping被有效的转换为FHE系统。

综上所述,我们这一期来仔细的探讨一下,GSW中提出的LFHE系统是怎么构造的吧~

PS:这一段回顾的内容仅仅是前两期描述的一小部分。所以如果大家看到这里对FHE的定义与LWE问题还是不够了解的话,不妨再回去看看之前的文章,然后再回来继续往下看。

构造GSW-LFHE系统的三次尝试

GSW系统是Gentry,Sahai,Waters三位大牛在2013年提出的第三代同态加密系统。整套加密系统围绕了一个核心概念:矩阵的近似特征向量。

乍一听,这个概念有点云里雾里的。所以整篇论文其实也分了三个阶段,循序渐进的来介绍这一系统的构造。这三个阶段中,每一个阶段都提出了一个LFHE系统的尝试,并且评估了这一尝试是否可行。

话不多说,我们这一期就来详细的学习一下Gentry在原文中对于LFHE构造的三次尝试,并且逐步的推导出最后GSW系统的全貌吧。

第一次尝试:矩阵的特征值与特征向量

d8J1Xqh8ibymndMe4TR5JlR5uRvEcyETddYfGzsU.png
VfmGaapzq7qvrg0G7nEXTYol0RciCQfPv69FmoYG.png
hCl3BmcEdtaYXwbUzh8Xg11nDG1HLWs5xsdMyVsn.png
tfFbieAFBSAbWjNGyH32PIk4adhqJvw0Iy2nhoin.png

“加密算法”的问题

我们的第一次尝试就完美的实现了全同态的所有要求,似乎看上去可以直接收摊,结束这篇文章了。

但是我们不能高兴的太早,因为这一体系有一个非常致命的弱点。如果细心的读者朋友们会发现,我们在讲述第一种方案的时候,一直给“加密”二字打上了引号。

I40AlYtYuuXTJRlleYYgs5SyordGw5nL9Oq7pYm6.png

但是这一架构对于我们后续的尝试是一个很好的启发,我们缺哪里补哪里就行了。上一期的文章中,我们讲到高斯消除法可以很好的找到线性方程组的解,但是如果我们叠加了一个噪音的话,就变成了困难的LWE问题。我们这里不妨也做同样的尝试,在特征向量与特征值的等式中加入噪音,看看会不会有所变化。

4ktEtTSHhL2VmoExArKekUgpGseU70FMVeqG5Ewa.png
7821yqvEiGmGHCZOyoYXW3Z4mJyA3v6ERwypQv5e.png
ScEpko3flqA1bXhYXvgbqu7pZvO88pOixtSGfV33.png
KPfsC3sU3zKr78wjYh3yCuyUOC9HQyfUQq1WZqfE.png
HiVr6XJJdqWvEy9RxGhrpfQqLmqoDQve06jZL0xN.png
0wWV2xN56biSWrHgzEjqTFuWeBEXyVgNTXsx0tFn.png
zyeVCdfobrJwtBBDUhqRkRthyQfyE0XcabtEuG3A.png
L0s2DvOviPNcHkdOgUYLGA2nynUEeDXuTzGWL90z.png
9PGbi69mibf93tzcGGUNNUBPezU3oBWHIINmCwni.png
0Ci1OBI16H73reS4Y7QQ22jxuRUuxe2KEb0Qp0Ok.png
KksVJhO8Yi5kivozjd6YyMZDU84jIWTdUAB02FCm.png
Smfv7q6UK6BU7GbfQvOCoX09P5uXmKJ8MdYhuacL.png
518LRX35S5pSOpudbn7uzOEAAWUdUykm5FzerWQy.png
CkAnjxCUh6Pc9HsXa2bpjAi3F2O2cBg61iAQpG48.png
1IsX0tP293muVkOO5wsC1KJEibAe16IjDG7k3fL9.png
EeDm27AtuS1abUJud1VpQ2vIrljr9b04XvtKdRwq.png
tnEK6JFZKrse75D0sTnkmgovatZB743uaLZob3oS.png
efMfvJDvHDncHZGvFzcQTnpH8Ni4bTSzVaWOgpym.png
CPHwLSXYzyIYBnXACx4wp6TzDJ4uekoj0aiUO7b4.png
msEKPtQOnpH3cn5lxIUM1geTBiX02dXTueOBkoT1.png
PDtEVBPI53kqWb4qxQDVwjp4TpA8tteeIGPMCipk.png

篇尾小结

相比起前两篇文章来说,这一篇文章可以说是最学术、数学公式最多的了。我尽可能地在描述的过程中用大白话来讲述LFHE系统的构造。如果大家在看的过程中还有一些疑惑,不妨把有困惑的地方再读一遍,或者私信我一起交流!

我在文章开头有所提到:GSW系统的精华就在于近似特征向量这么一个定义。我们从普通的特征向量出发构建了一个全同态、但是不加密的系统;随后,我们加入了LWE问题中类似的噪音向量,构成了一个部分同态、但加密的系统。最后,我们使用二进制分解这么一个工具,构成了GSW中最后提到的有限级数全同态加密系统。

看到这儿,如果你已经能get到GSW系统在做什么,是怎么来的的话,恭喜你已经掌握FHE系统构造的精髓啦!这是一件值得高兴的事情,因为FHE是一个相对来说非常年轻(~10年)的领域,我们已经站在密码学技术很前沿了。

下一步,是什么?

我们现在已经根据GSW这一篇paper所述的,一起构建出了一套LFHE系统了。但是就像我在第一篇中承诺的——我们要再接再厉,冲向真正的FHE。

(注:GSW的paper中讲到的加密算法和我们本文中提到的可能有所出入,使用的是一种非对称的形式,而我们用的是对称加密形式。但是这并不会影响整个体系的正确性或者是功能性。个人觉得这样更好理解一点。)

为了能够把LFHE系统转换为真正的FHE系统,我们就需要用到Gentry大佬提出来的Bootstrapping这一方法了。简单的来说,Bootstrapping可以把一个即将达到临界值的、带有很大噪音的密文,”刷新“成一个噪音很小的密文,这样就可以无限制的进行同态运算了。

下一期,我们详细的介绍一下GSW系统中是如何应用Bootstrapping把原本的LFHE转换为FHE的。篇幅允许的话,我们还可以来探讨一下现有FHE库(如HELib,SEAL,TFHE)等的区别。下期见啦~

来源:金色财经

敬告读者:本文为转载发布,不代表本网站赞同其观点和对其真实性负责。FX168财经仅提供信息发布平台,文章或有细微删改。
go