什么是全同态加密?

全同态加密属于密码学领域。由于全同态加密支持无需解密,就能够对密文进行任意计算,因此可以立竿见影的解决数据隐私安全问题,有很大的应用需求。例如,在云环境下,用户加密数据后存储在云端,由于数据加密使得云端无法获得数据的内容,从而保证了数据的隐私。此外,由于是全同态加密,云端可以对密文数据进行任意计算。总而言之,全同态加密不但通过加密保护了数据,而且没有丧失计算性。


全同态加密的概念早在1978年就提出,然后一找就是30多年过去了。当然这30多年也没闲着,30年间人们提出的方案随后就被证明是不安全的。
当然在这30年间,人们也退而求其次,能做一次加法和一次乘法的也可以,例如c1c2+c3c4,即一个二次多项式。这样的方案称为BGN方案。


当然再退而求其次,就是只能做加法,或者只能做乘法,这种方案称为单同态。例如,RSA就是乘法同态,Paillier就是加法同态。这些方案在有些地方大放异彩,尽管只能做一种同态计算。


直到2009年,Gentry,一个斯坦福大学的博士生,基于理想格提出一个全同态加密方案。Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In the 41st ACM Symposium on Theory of Computing (STOC), 2009. 这篇论文是来自于他的博士论文:Craig Gentry. A Fully Homomorphic Encryption Scheme (Ph.D. thesis).


世界哗然。各大报纸头条,密码学界的突破(Breakthrough),计算机界的突破。英文中Breakthrough可不是随便用的。
最为凑巧的是,09年左右恰好是云计算概念火热的时候。而所有介绍全同态加密的文章开头都会来一句,全同态加密用在云计算中可以保护数据隐私安全。谁催化了谁,真的不知道。


Gentry的全同态加密方案是基于理想格构造的。理想格为何物?通俗的说就是一种困难问题,就像大整数难题一样。
说到这里,不得不说两句格密码。很多人只知道RSA,ECC,但是提起格密码一脸的茫然与恐惧,觉得格密码一定是一个很难理解的问题。事实上,恰好相反,所谓的格(Lattice)就是整系数基的线性组合构成的点,通俗地说就是一个空间中的一些离散有规律的点。既然是离散的点,那么点之间一定有距离,距离产生美,从而产生了一些困难问题,例如:最短向量问题(SVP)。


如果是一个二维平面,那么寻找在格上寻找最短向量问题是简单的,但是当维数变大的时候,例如200多维,寻找格上的最短向量问题就变的异常困难,称之为格上标准困难问题,是一个指数级的困难问题。你可以想象一下,当你在迷宫里时(现实世界是3维的),找出口还不算很困难,但是当在一个200多维的迷宫里时,困难程度立刻指数级上升。


最令人感兴趣的是,格上标准困难问题至今没有量子算法可以破解或者撼动它,因此格上标准困难问题被认为是抗量子的。
格上的加密方案最大特征:是一个含有噪音的方案。加密时往里添加噪音,主要是为了进一步提高安全性。然而恰好是这个噪音,导致加密的形式与解密形式比较简单。这种特性为构造全同态加密埋下了伏笔。


话还是说回来,继续说全同态加密,否则讲格密码可以讲一千零一夜。那么30多年人们没有提出一个全同态加密方案,为什么Gtentry可以构造出来呢?
因为Gentry发现了一个方法:Boostrapping,该方法我把它称之为:同态解密。这个方法的作用是约减噪音。因为格上加密法案是噪音方案,即在密文中含有噪音,所以每次密文计算后,噪音都会增加,尤其是密文乘法导致噪音增长的非常快。即使你构造了一个具有同态性的加密方案,由于噪音增长,导致无法获得同态性。因此,约减密文计算后的噪音变得异常关键。当然在此之前应该构造一个具有同态性的方案。
Gentry是在格上首先构造一个具有同态性的加密方案,该方案能够做加法,也能够做乘法,但是只能做有限次的乘法。为什么呢?因为噪音的增长。噪音增长太快,使得无法继续密文计算。这样的方案称为:有限同态加密方案(Somewhat HE)。


如果想做更多的计算,怎么办呢?约减噪音,我想连小孩都会的有的常规想法。路线并不新颖,不知道是否让你失望了。关键是怎么约减?
Gentry观察到一个现象:如果解密的时候,输入的不是密文,而是对密文加密后的密文,同样,不是解密密钥,而是加密后的密钥,解密会输出什么东西呢?


答案:一个新的密文,该新密文依然是对原明文的加密。最重要的是新密文的噪音总是恒定的。
说到这里,你反应过来了么。这意味着每次密文计算后,如果使用同态解密操作,将会输出一个噪音恒定的新密文,这个新密文可以继续计算,计算后再同态解密,再计算,周而复始,无穷尽也,所谓任意计算实现了。


把密文再加密,密钥再加密后,输入到解密函数中,输出新的密文,这个方法就是Boostrapping技术,即:同态解密。
Gentry的论文,被号称是难以理解的。例如上面这个Boostrapping方法,当时我是理解的很久,因为它里面有很多技术细节。Gentry的博士论文也被号称没有几个人能够读懂。但是最后我是读懂了。


有了同态解密,全同态加密几乎被构造出来。几乎是因为Gentry构造的加密方案中,解密电路的深度太深,导致无法同态解密。为此,Gentry又发明出一个方法:压缩电路,将解密电路的复杂度降低,使得可以同态执行解密电路。你说复杂不复杂。
随后人们遵循Gentry 的思想提出了整数上的,小主理想上的,而且还进行了实现。但是依然很复杂。
然而,2012年有一个人Brakerski将全同态加密推上了顶峰,使之变的简单了,而且将全同态加密构件建在LWE问题之上。
LWE问题是一个格上的平均性困难问题,可以被归约到格上标准困难问题。也是抗量子的。目前主流的格上加密方案都是构建在LWE之上。
由于使用Boostrapping实现任意计算代价太高,而且现实中并不太需要任意计算,所以退而求其次,如果能够执行多项式深度的同态计算,也是能够满足大多数需求的。所以随后的LWE上的全同态加密不使用Boostrapping技术约减噪音,而是使用其它噪音约减技术,使得能够进行多项式深度的密文计算,代价大大降低了。


总之,目前只有在格上建立的全同态加密方案是安全的。建立的方法就是首先建立一个有限同态加密方案(SWHE),然后使用噪音约减技术,使之成为一个能够执行多项式深度同态计算的方案,称之为层次型全同态加密。


全同态加密的效率也是飞速提高,目前执行一次乘法在毫秒级,密文与明文之比约为10^2。微软去年初在人工神经网络上执行密文计算,效果是令人满意的。
全同态加密目前处在工程化研究阶段,相信全同态加密很快就会进入实践。

免责声明:本文章仅代表作者个人观点,不代表本站的立场和观点。本文章仅供信息分享,不构成对任何人的任何投资建议。本站作为中立的平台服务提供方,尊重他人的知识产权、名誉权等法律法规所规定的合法权益!如网页中刊载的文章或图片涉及侵权,请提供相关的权利证明和身份证明发送邮件到qklwk88@163.com,本站相关工作人员将会进行核查处理回复

本文地址:https://www.5m88.com/post/174.html

发布于 2022-03-04 00:03:00
收藏
分享
海报
0 条评论
2284
上一篇:什么是链上扩容和链下扩容? 下一篇:新加坡对俄罗斯银行、加密货币交易实施制裁
目录

    推荐阅读

    0 条评论

    请文明发言哦~

    忘记密码?

    图形验证码