资源描述：
《整数上的同态加密报告DGHV》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、整数上的同态加密报告1一、介绍与历史。lx基本概念①全同态加密用一句话来说就是：可以对加密数据做任意功能和任意次数的运算，运算的结果解密后是对明文做同样运算的结果。用处：云计算，安全多方计算，加密搜索，电子投票等。例Caesar密码对链接操作具有同态性。Caesar密码是一种循环移位替换加密体制。设密钥为O(1到26之间的整数)，明文为某个字母◎,则对应密文为字母表(循环使用)中O之后的第◎个字母。例如，取密钥为13。则有：cl=Encrypt(13,HELLO)=URYYB,c2=Encrypt(13,WORLD)=JBEYQo现记：c3=C
2、oncat(cl,c2)=URYYBJBEYQ,贝ijDecrypt(13,c3)=HELLOWORLD=Concat(ml,m2)o②一个比喻。有一位首饰商人Alice为了防止工人在制作首饰的过程中盗窃材料，想出了一个办法。她向一家公司定做了一种箱子。该箱子是带有挂锁的，钥匙只有Alice本人持有。箱子两侧有两个手套，工人可以在箱子外面使用手套来操作放在箱子里面的金银等材料来制作首饰。制作完成后，Alice使用钥匙打开箱子，拿出制作好的首饰。这样就实现了让工人在不直接接触材料的条件下对材料进行加工的目的。③历史同态加密的思想其实很早就有了。1
3、976年，Diffie和Hellman提出公钥加密思想，1977年第一个实用的公钥加密方案，同时也是历史上最成功的，直到现在仍有广泛应用的公钥加密体制RSA体制由Rivest,Shamir和Adleman提出。同年由Rivest,Adleman和Dertouzos提出了全同态加密的思想,最初被称为隐私同态。这是因为他们发现RSA算法本身就具有乘法同态性。此后，人们一直致力于寻找全同态加密算法。但在2009年之前的很长时间里都没有获得满意结果。只获得了一些半同态的或者仅能做有限步的全同态加密方案。2009年，IBM实习研究员(斯坦福大学博士研究生
4、)Gentry发明了一种基于理想格的全同态加密方案,发表在ACMSTOC2009国际会议上,获得了一致高度评价。但该方案复杂度太高，很难实用化。2010年，Dijk,Gentry等人乂提出了另外一种更加简洁易懂的全同态加密方案：基于整数(环)的全同态加密方案(DGHV)o但该方案计算复杂度和开销仍然较大，难于实现。2011年，Brakerski和Vaikuntanathan基于环上LWE(Learningwitherror)问题构造了同态加密方案Bvllao2011年，Brakerski>Gentry和Vaikuntanathan构造了BGV方
5、案。这是目前效率最高的全同态加密方案。同年，Gentry和Halevi对该方案进行了改进，提出了GHS方案。2012年,Halevi和Shoup利用C++语言和NTL数学函数库编写了实现BGV方案的软件包。二、基本概念1＞公钥密码体系：一个公钥密码体系£由3个算法组成：KeyGen,Encrypt,Decrypt,且这三个算法必须是高效的，即其运行时间最大为安全参数入的某个多项式poly（入）。KeyGen使用安全参数入生成两个密钥：公钥pk和私钥skoEncrypt（pk,m）使用公钥pk将消息（明文）m映射为密文CoDecrypt使用私钥s
6、k将密文c映射为明文mo2、（公钥）同态加密方案：除了上述3个基本算法之外，述有一个Evaluate算法。基本形式为：Evaluate£（pk,,f,q,c2»…5）。基木作用是输出f©,c2,…c』。＞1为了保证同态性，必须使得f（c—C2，…c』解密后的结果为f（mlf叫，…mJ,即：Decryptj（ci，c2»・••"）］=f（mlfm2,…mJ注：①满足该式子的函数f称为允许函数，所有允许函数的集合称为允许函数集合。②这里使用布尔电路来描述函数f。这是为了有效地表示f的复杂度。用布尔电路可以将f分解为简单的布尔电路的组合，如and电路
7、、xor电路等。And电路对应两个二进制数相乘，xor电路对应两个二进制数相加，且这两个电路是完备的。3、基本要求：（解密）正确性；保密性（Evaluate不会泄露关于f的信息）；紧凑性（输出密文c的长度与f无关人语义安全性（可以对抗CPA攻击）；三、整数上的全同态方案（DGHV）1、全同态加密基本方案的构造步骤①构造一个类全同态加密方案，即只能支持有限次全同态操作的方案。②通过一种自举技术将类全同态方案转化为全同态方案。Alice的问题：Alice发现了新的问题。她所订购的箱子是有问题的，即用一段时间之后，在得到成品之前箱子就坏掉了。Alic
8、e很牛气。她一方面起诉了为她制作箱子的公司，一方面自己思考该如何解决问题。在一个做噩梦醒来之后，她突然想到一个方法。她首先将所有箱子编号。然后把材料放
