《用于双线性型的高效同态加密方案的制作方法》由会员分享，可在线阅读，更多相关《用于双线性型的高效同态加密方案的制作方法（4页珍藏版）》请在金锄头文库上搜索。
1、用于双线性型的高效同态加密方案的制作方法专利名称：用于双线性型的高效同态加密方案的制作方法技术领域：本发明的示例性实施例通常涉及加密和解密算法，且更具体而言，涉及用于双线性型的同态加密方案。背景技术：支持对加密数据的操作(例如同态加密)的加密方案在安全计算中非常有用。同态加密方案是指这样的加密方案，其中，在两个或更多个密文上执行的一个或更多个操作(例如加法、乘法)转化为被解密的明文(即密文的解密)。例如，如果密文之和(CfC2)的解密产生相应的明文之和(BfB2)(可能模上(modulo)某个值)dec (CC2) BJB2，则可称加密方案是加法同态的。许多公钥密码系统支持加密数据的相加或相乘
2、，但要同时实现两者看来很难。 已知使用例如Yao的“加密电路”(garbled circuit)技术16，12,可以实现对加密数据来计算任意函数，但是密文大小以及解密复杂度至少会随着被计算的电路中的门数而线性增加。此外，Sander等15描述了一种允许评估任意电路的技术，但是密文大小随着电路深度成指数增加。这两种方法都可以仅使用“一般难度假设”(例如双流不经意传输协议(two-flow Oblivious-Transfer protocol)的存在等)来实现。Boneh、Goh和Nissim描述了一种密码系统,其允许任意数量的加法和一次乘法，而不会增加密文大小5。该方案在这里被称为BGN密码系
3、统。BGN密码系统的安全性基于允许双线性映射(bilinear map)的组合阶群(composite-order group)中的子群成员问题(sub-group membershipproblem)0该密码系统直接隐含了一种用于评估2-析取范式(2DNF)公式(或更一般地双线性型)的高效协议。Boneh等还描述了应用BGN密码系统来改进私密信息检索方案(PIR)的效率以及用于投票协议(voting protocol)。更近以来，AguilarMelchor、Gaborit 和 Herranz 在2中描述了一种“模板”，其用于将某些加法同态的加密转换为同时允许加法和乘法的加密系统。他们示出了
4、如何使用该模板来将BGN密码系统与Kawachi等11的密码系统进行组合，由此获得一种密码系统，其支持两次乘法和任意加法，基于子群成员问题和格(lattice)中唯一最短向量问题两者的难度。他们还示出了如何将该模板与Aguilar Melchor等I的密码系统一起使用，以获得无限制的乘法深度，其中密文大小随着乘法深度成指数增加，但支持加法而不会增加大小。(该最后实现的安全性基于相对未被研究的难度假设，其被称为“微分背包向量问题，(Differential Knapsack Vector Problem)。已知人们可以从格或线性码来构造加法同态加密方案。密文中隐性地包含“误差”，其随着密文被一起
5、操作(例如相加、相乘)而增长。因此，所产生的密文不会具有和原始密文(例如和单独解密的)一样的分布，并且在某个点上，误差会变得足够大从而引起错误的解密。为此，在该情形下，同态有时被称为“伪同态”(pseudohomomorphism)或“限界同态，(bounded homomorphism)。最近，Gentry描述了一种完全同态的密码系统9，其支持多项式数量(polynomially many)的加法和乘法,而不会增加密文大小，其安全性基于在理想格(ideallattice)中找到最短向量的难度8。发明内容在本发明的一个示例性实施例中，一种计算机可读存储介质有形地体现了可由机器执行以执行操作的指
6、令程序，所述操作包括接收信息B，该信息B将根据包含加密函数的加密方案被加密为密文C ;以及根据该加密方案的加密函数来加密信息B以获取密文C，其中，所述加密方案使用对应于至少一个私钥T的至少一个公钥A，其中所述信息B、密文C、至少一个公钥A和至少一个私钥T是矩阵，其中，所述加密函数接收至少一个公钥A和信息B作为输入，并将密文C输出为C AS+pX+B (modq)，其中S是随机矩阵，其中X是误差矩阵，其中P是整数，其中q是奇素数。在本发明的另一示例性实施例中，一种装置包括至少一个存储介质，其被配置为存储信息B，该信息B将根据包含加密函数的加密方案被加密为密文C ；以及至少一个处理 器，其被配置为
7、根据该加密方案的加密函数来加密信息B以获取密文C，其中，所述加密方案使用对应于至少一个私钥T的至少一个公钥A，其中所述信息B、密文C、至少一个公钥A和至少一个私钥T是矩阵，其中，所述加密函数接收至少一个公钥A和信息B作为输入，并将密文C输出为C AS+pX+B (modq)，其中S是随机矩阵，其中X是误差矩阵，其中P是整数，其中q是奇素数。在本发明的又一示例性实施例中，一种计算机可读存储介质有形地体现了可由机器执行以执行操作的指令程序，所述操作包括接收密文C，该密文C将根据包含解密函数的加密方案被解密为信息B ;以及根据该加密方案的解密函数来解密密文C以获取信息B，其中，所述加密方案使用至少一
8、个私钥T，其中所述信息B、密文C和至少一个私钥T是矩阵，其中，所述解密函数接收至少一个私钥T和密文C作为输入，并根据B=T4 (TCTtHiodq) (Tt)-1Hiodp来输出信息B，其中P是整数，其中q是奇素数。根据本发明的再一示例性实施例，一种装置包括至少一个存储介质，其被配置为存储密文C，该密文C将根据包含解密函数的加密方案被解密为信息B ；以及至少一个处理器，其被配置为根据该加密方案的解密函数来解密密文C以获取信息B，其中，所述加密方案使用至少一个私钥T，其中所述信息B、密文C和至少一个私钥T是矩阵，其中，所述解密函数接收至少一个私钥T和密文C作为输入，并根据B=T4 (TCTt m
9、odq) (Tt)-1Hiodp来输出信息B，其中P是整数，其中q是奇素数。根据本发明的又一示例性实施例，一种计算机可读存储介质有形地体现了可由机器执行以执行操作的指令程序，所述操作包括接收信息B，该信息B将根据包含加密函数和解密函数的加密方案被加密为密文C ;以及根据该加密方案的加密函数来加密信息B以获取密文C，其中，所述加密方案使用至少一个公钥A和对应于该至少一个公钥A的至少一个私钥T，其中所述信息B、密文C、至少一个公钥A和至少一个私钥T是矩阵，其中B e 2C e SJixm3 A e 且T e SJxm，其中n表示安全参数且m，q =poly ()，其中q是奇素数，其中P是整数，其中
10、qP，其中，所述加密函数接收A和B作为输入，并将密文C输出为C AS+pX+B (modq)，其中S是随机矩阵且S i其中X是误差矩阵且其中#是误差分布，其中是由 = l/Poly(n)给出的高斯误差参数，其中，所述解密函数接收T和C作为输入，并根据B=T4 VTCTt modq) -(Tt)modp来输出信息B，其中，所述加密方案是同态的并支持计算双线性型。通过下列详细描述并结合附图，本发明的实施例的上述和其他方面将变得更为明显，在附图中图IA示出了根据本发明的示例性实施例的示例性加密操作/函数；图IB示出了根据本发明的示例性实施例的示例性解密操作/函数；图IC示出了根据本发明的示例性实施例
11、的示例性密钥生成(KeyGen)操作/函 数；图ID示出了根据本发明的示例性实施例的示例性密文加法操作/函数；图IE示出了根据本发明的示例性实施例的示例性密文乘法操作/函数；图IF示出了根据本发明的示例性实施例的示例性“简单解密”操作/函数；图2示出了系统的框图，本发明的各种示例性实施例可以在该系统中实现；图3描述了逻辑流图，其示出了根据本发明的示例性实施例的示例性方法的操作以及示例性计算机程序的操作；图4描述了另一逻辑流图，其示出了根据本发明的示例性实施例的示例性方法的操作以及示例性计算机程序的操作；图5描述了又一逻辑流图，其示出了根据本发明的示例性实施例的示例性方法的操作以及示例性计算机程
12、序的操作；图6描述了再一逻辑流图，其示出了根据本发明的示例性实施例的示例性方法的操作以及示例性计算机程序的操作；且图7描述了又一逻辑流图，其示出了根据本发明的示例性实施例的示例性方法的操作以及示例性计算机程序的操作。具体实施例方式I.简介本发明的示例性实施例构造了一种简单的公钥加密方案，其支持计算双线性型(例如多项式数量的加法和一次乘法)，类似于Boneh、Goh和Nissim的密码系统(BGN)。安全性基于带误差学习(learning with errors,LWE)问题的难度，已知该问题和某些最坏情形的格问题难度一样。示例性密码系统的某些特征包括支持大的消息空间、容易获得公式私密性、比BG
13、N有更好的消息到明文扩张率、以及容易将两个加密的多项式相乘。此外，可以使得该方案是基于身份且泄露弹性的(leakage resilient)(以更高的消息到明文扩张率为代价)。这里对“z”的任何和所有提及(例如ZJTxti 都应被理解为对应于所有整数的集合。此外，这里对秘密、密钥或陷门(trapdoor)的任何和所有提及都应被理解为对应于私钥(例如，如在公钥一私钥加密方案中)，反之亦然。这里使用的术语是为了描述本发明的各种示例性实施例的目的，而不是要限制本发明。如这里所使用的，单数形式“一个”和“该”旨在也包含复数形式，除非上下文明确另外说明。还应该理解，术语“包含”和/或“包括”在本说明书中
14、使用时，表示所述特征、整体、步骤、操作、元素和/或组件的存在，但不是要排除一个或多个其他特征、整体、步骤、操作、元素、组件和/或其组合的存在或添加。I. I.引言在本文中，描述了一种示例性加密方案，它是加 法同态的，并且还支持一次乘法。该示例性方案基于Gentry、Peikert和Vaikuntanathan10提出的陷门函数(以下将被称为GPV陷门函数)。在GPV陷门函数中公钥”是矩阵A (对于参数q P且m n)，且相应的陷门是具有小的条目的满秩整数矩阵TeZmxm，从而TA = 0(mod q)。该示例性密码系统中的公钥和私钥和GPV陷门函数中的完全一样。通过设置C = AS+pX+Bm
15、odq来加密矩阵BeZrW其中，S是随机“系数矩阵”SeZf*且X是具有条目的 59“噪声矩阵”x e Zmxm，从而X的条目比q要小很多。密文矩阵可以被相加，并且支持单次矩阵相乘C= C1 -C； mod(/(Ct是c的转置矩阵)。为了解密，令B = T-1 (TCTtIiiodq) (Tt)-1Iiiodp示例性方案的安全性等价于带误差学习(LWE)的难度。该问题与众所周知的“具有噪声的奇偶性学习”(learning parity with noise)相关,它在基于格的密码学的研究中已经成为标准。该问题最初由Regev 14提出，并由Regev 14和Peikert 14表明，它和整数格
16、中的各种问题的最坏情形实例的难度一样。这里简要地指出，LWE问题与关联误差分布相关。I. 2 贡献该示例性方案与以前的工作的主要区别可能在于作为基础的难度假设。特别地，示例性方案是所报告的第一种基于LWE且不限于加法同态的密码系统。此外，示例性方案非常高效它可以在时间内对Hi2个元素的矩阵进行加密，且解密所花的时间相当。示例性方案与BGN密码系统的一个重要区别是，BGN密码系统只能对来自小的空间的消息加密(因为在解密时，只能恢复群元素gm，并且然后需要搜索消息m)。在示例性方案中，可以对于任何P对Zp上的矩阵加密，只要q比P足够大。一个相关的优势是，通过选择大的模数P，可以使得示例性方案具有0(1)的密文扩张(而BGN密码系统将O(Iogn)比特的明文扩展为0(n)比特密文)。需要注意，在示例性方案中定义消息空间的模数P可以由加密机动态选择同一公钥/私钥对可以被用来加密/解密消息模上很多个不同的域(或环)。
