中期检查报告.docx

中期检查报告.docx

《中期检查报告.docx》由会员分享，可在线阅读，更多相关《中期检查报告.docx（12页珍藏版）》请在冰点文库上搜索。

硕士学位论文中期检查报告

北京航空航天大学计算机学院

硕士学位论文中期检查报告

论文题目：

银行云计算中同态加密算法研究

专业：

计算机软件与理论

研究方向：

数据安全，加密技术

研究生：

学号：

指导教师：

北京航空航天大学计算机学院

2016年07月26日

北京航空航天大学计算机学院·10·

目录

1 论文工作计划 1

1.1论文选题背景 1

1.2论文研究目标 2

1.3论文主要研究内容 2

1.4论文工作计划 2

1.5预期成果 2

2 已经完成的工作 3

2.1国内外同态加密方案分析 3

2.2Fp上全同态加密方案的设计 4

3 关键技术 7

4 下一阶段工作计划 8

4.1存在的问题 8

4.2尚未完成的工作 8

4.3解决问题的技术思路或措施 8

4.4下一阶段计划 9

5 主要参考文献 9

银行云计算中同态加密算法研究

1论文工作计划

1.1论文选题背景

近年来，中小银行发展迅猛，在规模、效益等方面的提升上都取得很大的成绩，但由于资金，技术能力，运营维护等种种原因，很难通过自身实力建设IT系统，在此情况下，基于云计算的IT系统托管是解决该问题的最佳途径。

但银行业有其特殊性，对数据安全性、私密性的要求远高于其它行业，基于云计算平台的银行系统，其所有用户的数据都放在云端，并通过网络进行数据传输，在云平台遭受攻击，或者存在管理漏洞、人为破坏安全管理制度等情况下，银行信息发生丢失、窃取等现象，对于用户而言是致命的。

如何保证云计算系统中数据不被随意盗取、查看和拷贝是云服务商面临的重大挑战。

云服务商除具备相应安全管理资质、建立安全管理制度之外，还应采取相应技术手段，从根本上杜绝银行所属数据的安全和私密，提高银行对云计算平台的信任等级。

采用数据加密技术是应对银行云计算中数据安全问题的重要途径。

传统的数据加密技术可解决数据存储及传输过程的安全，但对诸如账户金额、交易流水记录等银行无需暴露给云服务商且需要进行计算的关键业务数据，传统加密算法不再适用，因为该类数据在系统中需要随时根据用户交易情况进行更新和计算，而在加密状态下系统无法识别数据致使计算无法完成，目前该类数据均采用明文存储于云平台数据库中，不利于银行及用户数据安全和隐私保护。

在这种情况下，我们谋求一种既能确保数据安全与隐私，还可充分利用云平台计算能力的加密方法。

同态加密是一种基于数学困难问题的密码学技术，它具备如下性质：

对经过同态加密的数据进行操作得到一个输出，将这一输出进行同态解密，其结果与用同一方法操作未加密的原始数据得到的输出结果一致。

该类加密算法可使云计算平台即使不知道明文数据，也可对密文直接进行计算，银行获取计算结果密文后，解密即可得在本端对明文进行同样计算的结果。

基于同态加密技术，我们可以在加密的数据中进行检索、对比、计算等操作，得到正确的结果，而在整个处理过程中无需对数据进行解密，其重要意义在于，真正从根本上解决云计算等场景下用户将数据及其操作委托给第三方时的保密问题。

1.2论文研究目标

针对银行云计算场景下数据安全问题，开展数据同态加密算法研究。

面向银行应用场景，对原有算法适当改进或裁剪，有效降低算法复杂度和密钥长度，提高加解密运算效率，提出适用于银行云计算的同态加密方案，设计实现算法验证模型系统，并给出验证方法和测试结果。

1.3论文主要研究内容

面向银行云计算应用场景的全同态加密方案设计。

面向银行云计算应用场景的全同态加密方案的编码与实现。

1.4论文工作计划

序号

时间段

计划完成的工作

1

2015.12-2016.01

通用加密算法研究，同态加密方案的密码学基础学习

2

2016.02-2016.03

全同态加密方案构造思想和实现技术研究

3

2016.04-2016.06

面向银行云计算应用场景的全同态加密方案设计

4

2016.07-2016.09

面向银行云计算应用场景的全同态加密方案的编码与实现

5

2016.10-2016.10

测试模拟方案的性能，完成参数确定与bug修复

6

2016.11-2016.11

毕业论文撰写

1.5预期成果

1.面向银行云计算应用场景的全同态加密方案

2.面向银行云计算应用场景的全同态加密方案的模拟实现系统及测试数据

3.小论文2篇

4.相关专利1项

2已经完成的工作

2.1银行云计算中同态运算需求分析

在调研部分中小银行相关情况后，根据银行业务逻辑和中小银行体量特点，分析预测云计算环境中银行数据的同态加密需求。

数据种类：

银行账目，主要是账户余额、交易额、利息率等数值类数据，为一定精度的实数；

数据精度：

小数部分保留3位有效数字（十进制）；

数据长度：

按照一定的密钥更换周期，预测该段时间内中小银行交易量，结合数据精度要求，确定需加密的数值可用48bit定点数表示；

同态运算次数：

根据中小银行交易量，预测其同态运算次数需求为216-232。

2.2国内外同态加密方案分析

通过对国内外同态加密领域的大量文献阅读和分析，将已发表的同态加密方案分为三个类别。

1.基于同态解密技术的自启动方案

2009年IBM研究员Gentry构造出第一个全同态加密方案，其后发表的多个方案都遵循Gentry的构造框架，在各种环的理想上，首先构建一个部分（somewhat）同态加密方案（即方案只能执行低次多项式计算），然后“压缩”解密电路，从而执行自己的解密函数进行同态解密，达到控制密文噪声增长的目的，通过迭代，最终理论上实现真正意义的全同态。

代表方案有2010年由Dijk，Gentry，Halevi和Vaikuntanathan联合提出的整数上的全同态加密方案（DGHV方案），实现了1-bit数据的全同态加密；2013年Cheon等人提出了批量全同态加密方案，可一次性加密多比特数据，提高了效率；2015年KNuida等提出了非二进制空间上的同态加密方案，可实现比特串的批量加密。

尽管同态解密是实现全同态加密的基石，但是同态解密的效率很低，同时，该类方案目前仅实现单比特或比特流的加密，对银行云计算下的数值（一定精度和长度的实数）计算不适用，需进行一定的改进。

2.无自启动的层次型同态加密方案

为规避由于同态解密带来的高复杂度，部分学者打破原有的Gentry构建全同态加密方案的框架，基于环上LWE问题构造无需自启动实现一定次数（多项式次数）的同态加密方案，以适用部分场景。

其基本思路是首先构建一个部分同态加密方案，密文计算后，用密钥交换技术控制密文向量的维数膨胀问题，然后使用模交换技术控制密文计算的噪声增长。

通过上述方法不需要同态解密技术就可获得层次型全同态加密方案，但该类方案并不是真正的全同态，由于其计算次数需要在方案设计时充分预估，一旦超过该次数方案即失效，同时为实现密钥交换和模交换，对密钥长度等参数有较高要求，也不能完全满足银行云计算的需求。

3.不带噪声消减的同态加密方案

上述两类方案在使用中均由于密文噪声在同态乘法中的快速增长而设计了各种消减措施，因而使得计算复杂度很高或者计算次数受限，这使得一些人开始探讨无噪声消减的同态加密方案。

2015年，MasahiroYagisawa、DongxiLiu、Li&Wang分别利用八元环、向量和非交换环的性质结合模运算提出了各自的无噪声消减的同态加密方案，构造方法简单易懂，相比上述两类方案效率有很大的提高，但由于其线性映射关系较为明确，安全性较低，需要进一步改进。

2.3Fp上全同态加密方案的设计

参照DGHV方案，为更好的适应本课题需求，对其进行改进，将其明文空间由单比特的F2拓展到有限数域Fp，构造方法表述如下。

Somewhat方案

按照DGHV方案中的相应参数进行设置。

l参数设置

γ公钥中整数的比特长度：

η私钥的比特长度；

ρ噪声的比特长度；

ε明文的比特长度；

ξ有限素域Fp中p的比特长度。

这些参数需满足以下条件：

r=w（loglε），为保证方案能够抵抗对噪声的蛮力攻击；

h≥r·Θ（lεlog2lε），这是为了能够计算压缩后的解密电路；

g=w（h2loglε），为了能够抵御各种对近似最大公因子问题的基于格的攻击方；

x≤Θ（hloglε），为了保证噪声不超过阈值，使得方案正确；

e≤x/2，是为了保证明文m属于有限域Fp，从而可以应用本节方案。

我们也使用另一个噪声参数r’=r+w（loglε），一个简便的参数设置方法就是令r=lε，r’=2lε，h=Θ（λε2），g=Θ（λε5）。

l对称加密方案

本方案可加密任一小于p的整数，而无需再将该整数转化成二进制数后再逐比特加密，进而可以大幅度提高方案的效率。

明文空间为Fp，即m∈{0,1,⋯,p-1}，其中p为素数，密文空间为C。

KeyGen（lε）：

在区间2Z+1⋂[2η-1,2η）选择一个h比特的素数s作为密钥。

Encrypt（Kp,m）：

对任意的整数m∈{0,1,⋯,p-1}进行加密，计算c=m+sq+pr，其中q∈（2γ-1,2γ]和r∈（2ρ-1,2ρ）是随机选取的整数。

DecryptKs,c：

输出m¬（cmods）modp。

改进之后还有一个问题，就是修改后的方案对于整数上的乘法和加法是否仍然保持同态性质?

下面验证其同态性：

设c1=m1+sq1+pr1,c2=m2+sq2+pr2,则有

Em1+Em2=c1+c2=m1+sq1+pr1+m2+sq2+pr2=m1+m2+sq1+q2+p（r1+r2）=Em1+m2

Em1×Em2=c1×c2=（m1+sq1+pr1）×（m2+sq2+pr2）=m1×m2+sm2q1+m1q2+pr1q2+pr2q1+sq1q2+p（m1r2+m2r1+pr1r2）=Em1×m2

下面我们讨论一下噪声的情况，若m+pr

此时能够从密文c中正确还原出明文m。

否则若m+pr≥s/2，解密就有可能出现错误。

接下来我们将上述方案调整为公钥加密方案。

l公钥加密方案

KeyGen（lε）：

选取一个素数s∈[2η-1,2η]作为私钥，随机选择一个素数q∈2q-1,2q，再随机选取两个整数l∈[0,2γ/s]和h∈（-2ρ,2ρ），令N=sq，计算x=sl+ph。

输出公钥Kp=（N,x），私钥Ks=s。

EncryptKp,m：

随机选择两个整数r1∈（-2r’,2r’），r2∈（-2r,2r），根据公钥Kp=（N,x），计算C=（m+pr1+r2x）modN，输出c。

DecryptKs,c：

输出m¬（cmods）modp。

EvaluateKp,C,c1,⋯,cg：

对于给定的电路Cε，以及g个密文ci，用整数上模N的加法和乘法门替换原电路中的加法和乘法门，将g个密文输入到扩展的电路后，执行其中所有的运算，最后输出电路的运算结果。

注意为了能够正确解密，这里需要保证cmods的取值在（-s/2,s/2）之间。

l解密正确性

这个方案的噪声为cmods，而c=m+pr1+r2h+sr2l-kq，所以在解密过程中首先计算的是c/s，而实际上相当于求c除以s的整数商r2l-kq。

因为

c/s=m+pr1+r2hs+r2l-kq

因此为了能够满足：

c/s=r2l-kq，就要满足下面的条件

|m+pr1+r2hs|<12

即

m+pr1+r2h

进而有c-c/s=m+p（r1+r2h），解密过程的下一步就是对c-c/s进行模p运算。

因为m

全同态加密方案

为实现方案的全同态，需要参照DGHV方案对解密电路进行压缩，使其变为方案的可计算电路。

为了进行压缩我们还需引进另外一些参数：

κ=γηρ',Θ=ωκlogλε,λ'ε=λε,κ'=γk'/ρ'。

KeyGenε：

从[2η-ξ-1,2η-ξ）中随机选择一个素数t，计算s=pt+1，且满足s/2仍为素数，若不满足则重新选取t。

私钥为Ks=s，调用原方案的KeyGenε算法，产生公钥Kp=（N,x）。

设置xs=[2κ/s]，随机选取一个汉明重量为λ’ε的Θ维向量s=s1,s2,…,sΘ，然后根据向量s获得一个集合S=i:

si=1，可知S中的非零元素个数为λ’ε。

在[0,2κ+1]中随机选择Θ个整数ui，其中i=1,2,…,Θ，使得i∈Sui=xs（mod2κ+1），再令yi=ui/2κ，得到向量y=y1,y2,…,yΘ，其中

i∈Syip=i∈Sui2κp=[（i∈Sui）/2κ]p=[（xsmod2κ+1）/2κ]p=[（[2κ/s]mod2κ+1）/2κ]p=[（2κ/s）2κ]p=[1/s]p=1/s-|∆s|

Encryptε：

按照原方案Encryptε算法对明文m进行加密生成密文c*，然后令zi←[c*∙yi]p，其中i=1,2,…,Θ，每个保留n比特精度：

n=logθ+3，输出c*及z=z1,z2,…,zΘ。

Decryptε：

输入c*，z以及私钥s，计算m'←[c*-sizi]p，输出m。

Evaluate：

给定电路Cε，然后用整数上的模N的加法和乘法门相应的替换原来电路中的二进制加法和乘法门，将密文c1,c2,⋯,cg输入到替换所得到的新电路中，为了保证运算后能够正确解密，则需要在密文进入运算门前先对其进行提取主密文c*的操作；然后对主密文c*进行刷新，将刷新后的主密文c*'输入到运算门进行运算。

输出c*''，再对c*''进行扩展得到新的密文c'=（c*'':

z''），如此进行下去，直到运算结束，最终将所得到的结果输出。

2.4其它具体工作

1.以有限数域上的同态加密方案为主要内容的一篇小论文《AFullyHomomorphicEncryptionSchemeoverFinitePrimeField》由2016云计算、物联网与信息科学国际会议（CCITIS2016）收录，将进入EI索引。

2.《一种传送和处理数据的方法及系统》专利申请已被受理。

3.同态加密实验相关代码约1000行。

主要为DGHV方案和基于非交换环的不带噪声消减方案的复现。

3关键技术

上述的明文空间为Fp的整数上的全同态加密方案采用的关键技术为同态解密技术，其主要目的在于有效解决同态运算后密文噪声快速增长的问题。

前文中提到，对于DGHV等方案，其密文噪声为m+pr，要求m+pr

此时能够从密文c中正确还原出明文m，反之，若m+pr≥s/2，则在模s运算中会因有效信息的丢失导致解密失败。

同态运算中，加法运算使噪声随着运算次数线性增长，但乘法运算将使得噪声随运算次数指数增长，即使将参数s设置很大，也将很快由于噪声超限造成无法解密，因此必须对运算后产生的结果密文进行噪声消减。

同态加密即将结果密文及相应的密钥分别加密后输入evaluate，在evaluate算法中同态执行解密电路将输出一个新的密文（称为密文更新），该密文解密后还是原来的明文，但其噪声已恢复到新鲜密文的量级。

如果新密文的噪声还允许进行一次乘法运算，那么在每次密文计算后，通过同态解密更新密文就可以进行下一次计算，递归上述过程就可以对密文进行无限次的计算，从而实现了全同态加密。

4下一阶段工作计划

4.1存在的问题

前文所述的基于DGHV方案改进的Fp上的全同态加密方案虽然将明文空间从单比特整数拓展到了一定长度的整数域，但依然与银行应用场景有一定距离。

银行实际需要带密运算的数据应为一定精度（小数点后3位有效数字）和长度的实数，不能直接采用该基于整数的加密方案，需要对数据进行预先处理。

4.2尚未完成的工作

基于DGHV方案改进的Fp上的全同态加密方案仅在理论上进行设计和正确性证明，目前尚未进行代码实验，需在实验中验证其正确性，并进行性能测试，与现有的其它方案进行对比分析，根据实验数据修改调整相关参数。

4.3解决问题的技术思路或措施

对于银行实际运行数据与所设计的同态加密方案中明文为一定长度整数的矛盾，可从两个方面考虑解决，一是将实数拆分为整数和小数两部分，对小数部分放大一定倍数转换为整数，两部分分别加密储存，同态计算中分开计算，并在方案中考虑进位等情况，二是继续研究其它现有的同态加密方案，若有明文空间更接近实际场景的，则更换为该构造方案并改进。

4.4下一阶段计划

1

2016.07-2016.09

继续进行面向银行云计算应用场景的全同态加密方案的设计，并通过实验确定最终方案

2

2016.10-2016.10

测试模拟方案的性能，完成参数确定与bug修复

3

2016.11-2016.11

毕业论文撰写

5主要参考文献

[1]GentryC.Fullyhomomorphicencryptionusingideallattices[C].Procofthe41stAnnualACMSymposiumonTheoryofComputing.NewYork:

ACM　Press,2009:

169-178.

[2]VanDijkM,GentryC,HaleviS,etal.Fullyhomomorphicencryptionovertheintegers[C]//AnnualInternationalConferenceontheTheoryandApplicationsofCryptographicTechniques.SpringerBerlinHeidelberg,2010:

24-43.

[3]BrakerskiZ,GentryC,VaikuntanathanV.FullyHomomorphicEncryptionwithoutBootstrapping.[J].AcmTransactionsonComputationTheory,2011,18（18）:

169--178.

[4]BrakerskiZ.FullyhomomorphicencryptionwithoutmodulusswitchingfromclassicalGapSVP[M]//AdvancesinCryptology–CRYPTO2012.SpringerBerlinHeidelberg,2012:

868-886.

[5]CheonJH,CoronJS,KimJ,etal.Batchfullyhomomorphicencryptionovertheintegers[C]//AnnualInternationalConferenceontheTheoryandApplicationsofCryptographicTechniques.SpringerBerlinHeidelberg,2013:

315-335.

[6]GentryC,SahaiA,WatersB.Homomorphicencryptionfromlearningwitherrors:

Conceptually-simpler,asymptotically-faster,attribute-based[M]//AdvancesinCryptology–CRYPTO2013.SpringerBerlinHeidelberg,2013:

75-92.

[7]NuidaK,KurosawaK.（Batch）FullyHomomorphicEncryptionoverIntegersforNon-BinaryMessageSpaces[C]//AnnualInternationalConferenceontheTheoryandApplicationsofCryptographicTechniques.SpringerBerlinHeidelberg,2015:

537-555.

[8]锡晓峰,曹宝香.一种适用于云计算环境的改进全同态加密方案[J].计算机技术与发展,2015

（2）:

144-147.

[9]YagisawaM.FullyHomomorphicEncryptionwithoutbootstrapping[J].https:

//www.lap-2015.

[10]WangY.Notesontwofullyhomomorphicencryptionschemeswithoutbootstrapping[R].CryptologyePrintArchive,Report2015/519,2015.http:

//eprint.iacr.org.

[11]LiuD.PracticalFullyHomomorphicEncryptionwithoutNoiseReduction[J].IACRCryptologyePrintArchive,2015,2015:

468.

[12]LiJ,WangL.Noise-freeSymmetricFullyHomomorphicEncryptionbasedonnoncommutativerings[J].Availableateprint.iacr.org/2015/641.

[13]GjøsteenK,StrandM.Fullyhomomorphicencryptionmustbefatorugly?

[R].CryptologyePrintArchive,Report2016/105,2016.http:

//eprint.iacr.org.

[14]李浪,余孝忠,杨娅琼,等.同态加密研究进展综述[J].计算机应用研究,2015,32（11）:

3209-3214.

[15]汤殿华,祝世雄,曹云飞.整数上全同态加密方案的重加密技术[J].信息安全与通信保密,2012

（1）:

76-79.

[16]YagisawaM.Improvedfullyhomomorphicencryptionwithcompositenumbermodulus[R].CryptologyePrintArchive,Report2016/50,2016.http:

//eprint.iacr.org.