整数上全同态加密方案分析

整数上全同态加密方案分析

ID:18954628

大小:235.00 KB

页数:26页

时间:2018-09-27

整数上全同态加密方案分析_第1页
整数上全同态加密方案分析_第2页
整数上全同态加密方案分析_第3页
整数上全同态加密方案分析_第4页
整数上全同态加密方案分析_第5页
资源描述:

《整数上全同态加密方案分析》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、整数上全同态加密方案分析一篇论文看完了,如果都看懂了的话,很多人觉得案例都是小菜一碟,但是在我写这个案例的时候我发觉论文看懂了,更需要案例或者说实现来进一步深入或者夯实,因为只有通过具体的实现步骤,才能发现有些在论文中的一些细节问题,反过来更可以促进对论文的理解。整数上全同态加密方案有两篇非常经典的论文,一篇是《FullyHomomorphicEncryptionovertheIntegers》以下简称DGHV方案,还有一篇是Gentry写的《ComputingArbitraryFunctionsofEncryptedData》简称CAFED

2、论文。入门者适合先阅读CAFED论文,这并不是说这篇论文简单,只是因为这篇文章的写法很通俗(严格意义上这篇文章并不是一篇真正的论文,是给杂志写的文章,有点科普性质),有一个很好的比喻的例子“Glovebox”贯穿于整个论文中,Gentry的文笔很好写的也很生动,对有些地方进行了背景解释,而这些解释恰好是DGHV论文中没有说的,当然一开始要想把CAFED论文彻底读懂也不是那么容易的。这个时候可以开始阅读DGHV这篇论文。这篇论文对于我来说是百读不厌,因为有些地方就算读了一百篇也不见得可以理解,而且这篇文章很适合深挖,有些很有趣的地方,例如噪声参

3、数的设置等等。还有一篇论文就是全同态的经典论文《Fullyhomomorphicencryptionusingideallattices》,如果对格不熟悉的话,可以读这篇文章的前面三分之一,因为有详细的全同态的定义、层级全同态、允许电路、增强解密电路、bootstrable、重加密原理,以及如何通过递归实现全同态的,尤其是递归实现全同态的过程,在论文中还是值得反复理解的。剩下的当然还有Gentry的博士论文,也可以分阶段阅读。这篇文章就算是一个阅读笔记吧,分为两个部分,一个是实现过程,另一个是方案的参数分析。一、方案实现过程1、全同态加密方案

4、至于什么是全同态等等形式化定义我就不说了,请参阅论文。全同态加密用一句话来说就是:可以对加密数据做任意功能的运算,运算的结果解密后是相应于对明文做同样运算的结果。有点穿越的意思,从密文空间穿越到明文空间,但是穿越的时候是要被蒙上眼睛的。另外上面的那句话是不能说反的,例如:运算的结果加密后是相应于对明文做同样运算结果的加密,这样说是不对的,因为加密不是确定性的,每次加密由于引入了随机数,每次加密的结果都是不一样的,同一条明文对应的是好几条密文。而解密是确定的。全同态具有这么好的性质,什么样的加密方案可以符合要求呢?往下看:Enc(m):m+2r

5、+pqDec(c):(cmodp)mod2=(c–p*「c/p」)mod2=Lsb(c)XORLsb(「c/p」)上面这个加密方案显然是正确的,模p运算把pq消去,模2运算把2r消去,最后剩下明文m。这个公式看上去很简单,但是却很耐看,需要多看看。公式中的p是一个正的奇数,q是一个大的正整数(没有要求是奇数,它比p要大的多),p和q在密钥生成阶段确定,p看成是密钥。而r是加密时随机选择的一个小的整数(可以为负数)。明文m∈{0,1},是对“位”进行加密的,所得密文是整数。上面方案的明文空间是{0,1},密文空间是整数集。全同态加密方案中除了加

6、密、解密还有一个非常重要的算法就是:Evaluate,它的作用就是对于给定的功能函数f以及密文c1,c2,…,ct等做运算f(c1,c2,…,ct)。在这里就是对密文做相应的整数加、减、乘运算。以上方案可以看成是对称加密方案。下面来考虑公钥加密方案。其实把pq看成公钥就OK。由于q是公开的,所以如果把pq看成公钥,私钥p立刻就被知道了(p=pq/q)。怎么办呢?看上面加密算法中,当对明文0进行加密时,密文为2r+pq,所以我们可以做一个集合{xi;xi=2ri+pqi},公钥pk就是这个集合{xi},加密时随机的从{xi}中选取一个子集S,按

7、如下公式进行加密:Enc(m):m+2r+sum(S);其中sum(S)表示对S中的xi进行求和。由于sum(S)是一些0的加密密文之和,所以对解密并不影响,整个解密过程不变。这个方案是安全的,就是我们所说的DGHV方案。其安全性依赖于一个困难问题“近似GCD问题”。就是给你一些xi,你求不出p来(由于整数上全同态研究热了,近似GCD也成了研究的一个点)。为了说明方便,我们还是采取pq为公钥的方案(尽管不安全,但是不影响说明过程)。所以加密和解密还是按照一开始的公式,现在pq为公钥,p还是私钥,q是公开参数。再重复一遍我们的加密解密算法:En

8、c(m):m+2r+pqDec(c):(cmodp)mod2=(c–p*「c/p」)mod2=Lsb(c)XORLsb(「c/p」)另外在这里约定:一个实数模p为:

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。