同态加密综述

《同态加密综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、信息系统安全题目：同态加密综述姓名••###学号：2013202110076武汉大学二◦-三年十月同态加密综述概念2009年，IBM公司的克南格•金特里(CraigGentry)发表了一篇文章，公布了一项关于密码学的全新发现：一项真正的突破。他发现，对加密的数据进行处理得到一个输出，将这一输ih进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。这听起来就像足不知道闷题也能给出问题的答案一样。记加密操作为E,解密为E;明文为m，加密得e,即e=E(m),m=E’(e)。已知针对明文奋操作f,针对E可构造F,使得F(e)=E(f(m))

2、,这样E就是一个针对f的同态加密算法。来源2009年9月，CraigGentry的论文发表于STOC。-•名IBM研究员解决了一项棘于-的数学问题，该问题A从几十年前公钥加密发明以来一直困扰着科学家们。该项创新为“隐私同态(privacyhomomorphism)”或“全同态加密(fullyhomomorphicencryption)”领域的重要技术突破，使得加密信息，即刻意被打乱的数据仍能够被深入和无限的分析，而不会影响其保密性。IBM研究员CraigGentry设计了这-•解决方案。他使用被称为“理想格ideallattice”的数学对象，使人们可以

3、充分操作加密状态的数裾，而这在过去根本无法设想。经过这一突破，存储他人机密电子数据的电脑销售商就能受川户委托来充分分析数裾，不川频繁与川户交瓦，也不必看到任何隐私数据。利用Gentry的技术，对加密倍息的分析能得到同样细致的分析结果，就好像原始数据完全可见一样。加密机理整数上全同态加密方案有两篇非常经典的论文，一篇足《FullyHomomorphicEncryptionovertheIntegers》以卜简称DGHV方案，还有一篇是Gentry写的《ComputingArbitraryFunctionsofEncryptedData》简称CAFED论文。

4、1、同态加密方案M态加密用一句话来说就是：讨以对加密数据做任意功能的运算，运算的结果解密后是相应于对明文做同样运算的结果。：W外上浙的那句话是不能说反的，例如：运算的结果加密后是相应于对明文做Ml样运算结果的加密，这样说是不对的，因为加密不是确定性的，每次加密由于引入了随机数，每次加密的结果都足不-•样的，同一条明文对应的足好儿条密文。而解密足确定的。Enc(m):m+2r+pqDec(c):(cmodp)mod2=(c-p*Tc/pJ)mod2=Lsb(c)XORLsb(「c/p」)上面这个加密力*案显然是正确的，模p运算把pq消去，模2运算把2r消去

5、，最后剩下明文m。公式中的p是-个正的奇数，q是一个大的正整数(没有要求是奇数，它比p要大的多),p和q在密钥生成阶段确定，p看成是密钥。而r是加密时随机选择的一个小的整数(讨以为负数)。叨文me｛0，1｝,是对“位”进行加密的，所得密文是整数。上而方案的明文空I川是｛0,1｝，密文空间是整数集。M态加密方案中除了加密、解密还有一个非常重要的算法就是：Evaluate,它的作用就是对于给定的功能函数f以及密文cl,c2,…，ct等做运算f(cl,c2,…，ct)。在这里就是对密文做相应的整数加、减、乘运算。以上方案可以看成是对称加密方案。对于公钥加密方案

6、，其实把pq看成公钥就OK。由于q是公开的，所以如果把pq看成公钥，私钥p立刻就被知道了(p=pq/q)o怎么办呢？看上面加密算法中，当对明义0进行加密时，密文为2r+pq，所以我们可以做一个集合｛xhxi=2ri+pqi｝,公钥pk就是这个集合｛xi｝,加密时随机的从｛xi｝中选取一个子集S，按如下公式进行加密：Enc(m):m+2r+sum(S);其中sum(S)表示对S中的xi进行求和。由于sum(S)是一些0的加密密文之和，所以对解密并不影响，整个解密过程不变。这个方案足安全的，就足我们所说的DGHV方案。其安全性依赖于一•个W难问题“近似GCD

7、问题”。就是给你一些xi,你求不Hip来(由于整数上全同态研究热了，近似GCD也成了研究的一个点)。为了说明方便，我们还是釆取pq为公钥的方案。所以加密和解密还是按照一开始的公式，现在pq为公钥，p还足私钥，q足公开参数。再重复一遍我们的加密解密算法：Enc(m):m+2r+pqDec(c):(cmodp)mod2=(c-p*Tc/pJ)mod2=Lsb(c)XORLsb(「c/pj)另外在这単.约定：一个实数模p为：amodp=a-「a/p」*p，「a」表示最近粮数，即有唯一整数在(a-1/2,a+l/2j中。所以amodp的范围也就变成丫(-p/2,

8、p/2J(这个牢记)。这个和我们〒时说的模p范围是不一样的，•〒时模p范围是10