广义自展技术基于块平等测试算法

文摘

与云计算和大数据的快速发展,数据存储和计算外包委托给不可信的云,导致一系列具有挑战性的安全和隐私的威胁。完全同态加密可以用来保护云数据的隐私和第三方解决信任问题。实现完全同态加密的关键问题是如何减少增加噪声在密文的评估。引导程序可以用大错误,刷新密文,这样生成的密文可能更小的错误,并允许被连续同态评估。在本文中,我们调查了引导程序用于构造完全同态加密方案。我们提出了一种新的块同态平等的概念测试算法和基于FH-SIMD方案给出了一个实例。此外,基于块同态平等测试算法,我们提出了一个快速引导程序引导较小的钥匙。理论分析和实验仿真验证我们的引导算法的高性能。

1。介绍

快速发展的云存储和计算平台允许用户委托数据外包到云服务器。云计算的特点是数据集中、资源共享、高度互连,完全打开,等。它打破了传统It领域的信息孤岛;与此同时,它带来了更加严重的安全问题。保护数据的隐私和商业秘密的保密,需要加密上传数据。然而,很难过程密文传统加密算法,这促进了改善和发展完全同态加密(FHE)。完全同态加密的突出优点是它可以解决密文评价问题。

2009年,绅士1,2)构造的第一个完全同态加密方案使用理想的晶格,支持任意深度电路评估。此后出现了许多完全同态加密方案涉及新的数学概念和NP困难问题和提高效率,例如从LWE FHE [3],环LWE [4)、整数(5),和轻水反应堆6]。

2010年PKC,聪明,比·[7)提出了一个变种的绅士与密钥和密文尺寸相对较小的方案。包装信息,允许我们用单指令多数据(SIMD)同态操作很多加密消息。聪明和Vercautren [8)表明,应用中国提醒定理(CRT)分区数量字段的信息空间绅士FHE计划为一个向量的明文槽,导致实质性的加速,该计划作为FH-SIMD表示。在工作,他们解释说,可以利用SIMD操作执行许多更高级别的操作,如执行AES加密homomorphically和搜索加密的数据库远程不受信任的服务器上。

绅士,Sahai和水域9)构建一个简单的同态加密方案从学习中的错误密码2013,叫GSW方案。在这项工作,他们提出了一种新的技术来构建FHE计划通过近似特征向量的方法。GSW的同态加法和乘法方案只是矩阵加法和乘法,这使得GSW计划渐近快和容易理解。否则,GSW计划经营单一位一旦加密和应以沉重的代价为评估大量暗文。

引导技术是核心技术完全同态加密(FHE),把“有点同态加密(她)计划为完全同态。即引导程序homomorphically评估她计划在密文的解密功能,不支持任何进一步的同态操作,并产生一个新的加密相同的消息,并可以处理更多的同态操作。

引导程序是计算非常昂贵,变得完全同态加密实用性的主要瓶颈。因此,有很多作品试图提高其效率。绅士,Halevi和智能9)提出了一个简单的方法,绕过使用模的同态modular-reduction瓶颈非常接近2的幂。2013年加密,Alperin-Sheriff和Peikert10)给完全代数算法引导拟线性时间。他们给homomorphically评估一种结构化的方法线性变换使用“ring-switching”过程,导致评估解密有效运转。

最近,Alperin-Sheriff和Peikert [11)提出了广义引导技术使用GSW方案。FHE方案的同态解密LWE总结内部生产和舍入操作,文本和同态方程算法的关键子过程舍入操作。嵌入加法群对称群 置换矩阵是另一种技术使用的工作(11]。

2015年Eurocrypt Ducas和Micciancio12]给出了一个有效的引导技术通过编码循环组根源集团的统一: ,在哪里是原始的 根的团结。这样就可以实现一个引导程序类似于Alperin-Sheriff和Peikert [11),但在每个循环组元素是由一个密文编码,而不是一个向量的密文,这有效地减少了引导的大小关键。

在AsiaCrypt2016 Chillotti等人构建一个有效的引导完全同态加密方案,称为TFHE [13]。运行引导的时间小于0.1秒。在AsiaCrypt2017 Chillotti et al。14)优化多个叫做加数的工作(13),引导时间减少13毫秒。2018年,周et al。15)优化串行叫做加数平行叫做加数,单一的速度引导门是更快的工作14]。TFHE方案和优化的版本都是单点引导程序(13- - - - - -15]。虽然很多努力花费在提高引导,有效的和有效的方法还有待发展。多位数和如何构建有效的引导过程值得进一步研究。

我们的研究结果。在本文中,我们研究同态平等测试算法在引导过程并提出了块同态平等测试算法的概念B_Eq吗?基于FH-SIMD方案并给出一个实例。此外,我们提出了一个更快的引导过程基于块同态平等测试算法。理论分析和实验仿真验证我们的引导算法更高的性能比Alperin-Sheriff和Peikert的工作(11]。

组织。节2在场上,我们描述一些预赛和同态和广义的概念引导技术。节3,我们提出了块同态平等测试算法B_Eq ?并给出基于B_Eq更快的引导程序?算法。节4,我们给予理论分析和实验仿真。我们给的结论部分5。

2。预赛

2.1。场和同态

让 首一多项式的学位 ,这完全分解到独特的不可约的因素如下: 在每一个多项式有学位 。

让表示代数 ,我们可以得到自然同态通过中国剩余定理(CRT):

为 ,有限的领域是一个分支,它 。让表示固定的正则表示 ,在哪里 一些不可约多项式的学位 让是一个固定的根源在代数关闭 。自包含在每个 ,有一个同态嵌入如下: 在哪里是一根在代数 ,也就是说,

根据CRT和上面的同态嵌入中,我们可以获得一个同态的嵌入在代数定义如下: 的多项式和通过CRT和计算如下: 从上面的定义 ,我们可以看到,地图的矢量二元多项式 每个人度不足 ,到一个多项式程度的不足 。地图定义了一个同构之间和 ,所以逆映射定义良好的来 。我们可以代表如下: 有两种方法来计算元素 :一个方法是明智的向量的计算组件元素 ;总结三个过程,首先,所有的输入映射到代数通过 ;其次,表现在代数计算 ;最后,映射结果返回通过 。此外,完全同态加密方案FH-SIMD执行一个评价l元素使用代数。

2.2。广义自展技术

绅士首先提出引导技术,变换一种同态加密方案完全同态加密方案。随后,雅各Alperin-Sheriff和克里斯Peikert [11)提出了广义引导技术。广义自展技术包括两个加密方案,外层加密方案和内心的加密方案。它执行解密程序内部加密方案使用外部加密方案,导致在密文减少错误。广义自展技术使得外层加密不同于内心,意识到我们可以设计相应的外层加密方案的具体内部加密方案,这样有效执行解密电路内部加密方案。因此,广义的引导比普通的更高效。

2.3。从LWE FHE的解密

所有完全同态的解密方案基于LWE涉及计算内部生产和舍入,也就是说,输入密钥 和二进制密文 ;解密算法是写成的 模块化的舍入函数在哪里 : 表明它的参数是否“远离”或“接近”0(模问),和模量问和维d都可以让小如准线性吗在安全参数通过dimension-modulus减少(3),同时还提供可证明的安全在传统点阵的假设。内积只是总结向量的元素选择性地, 假设 ,该算法可以被迭代解释为舍入 在哪里 表示平等的测试算法,当是平等的 , 输出1;否则, 输出0。

现在,我们给的解密算法基于FHE LWE密文状态。在引导过程中,秘密的密文 是写的 作为引导公共密钥。内积的密文状态表示 。和舍入算法在密文状态表示 ,“”表示在密文空间和同态之外指出了同态平等测试算法;它输出的密文1当且仅当 ;否则输出0的密文。我们让表示1和的密文表示0的密文。

2.4。从LWE FHE广义引导程序

假定二进制密文是引导 ,密钥是 ,和维和模块是足够小( )。从LWE FHE的解密功能方案 。我们也认为FH-SIMD外层加密方案,也就是说,FHE方案支持SIMD操作。广义自展技术总结两种算法:BootGen算法和引导算法(11]。(我)BootGen :输入密钥向量 ,和FH-SIMD的公钥加密;输出引导公共密钥 ,也就是说,加密密钥向量通过FH-SIMD方案和生成的密文为引导的公钥 。(2)引导 :输入引导公共密钥和密文向量 ,输出一个新的密文原来的加密方案基于LWE,解密的结果使用密钥 一样是解密吗使用密钥 ,但用更少的错误。

3所示。基于FH-SIMD更快的引导

3.1。主要思想

雅各Alperin-Sheriff和克里斯Peikert基于GSW方案提出了广义引导方法。广义同态平等测试是一个关键组成部分引导算法,即固定 ,在密文状态下,每一个 满足 ,并决定是否 ,见图1。

我们打算提出块同态平等测试算法,也就是说,它一块 , 满足 ,并决定是否这批退出一个这样 ,见图2。

求助于FH-SIMD同态加密方案(7),我们将一块同态平等测试算法B_Eq ?,然后propose an efficient generalized bootstrapping algorithm. The bootstrapping key is an encryption of each coordinate of the secret key ,,由FH-SIMD暗文。来引导 ,内积 计算homomorphically subset-sum使用另外的方法,而函数是计算使用块同态平等测试算法和添加方法。

3.2。块同态平等测试算法

在本节中,我们描述块同态平等测试算法,称为B_Eq ?。

输入:ciphertex和明文块 。

输出:如果出口 这样 持有,那么块homomophic平等测试算法输出 ;否则输出 。

我们假设和所有是位的长度,因此可以被编码为一个元素的有限的申请 ,在哪里 。描述的具体过程如下:

为 ,在每一个满足 ,嵌入每个坐标 的一个元素 。我们的目标是包成单个元素 ,所以我们计算 。然后计算的简单加密在代数一个使用FH-SIMD方案。值得注意的是,我们加密没有随机,这样节省计算成本。也就是说,

然后计算

总和的密文和 ,和表示的总和 ,也就是说,

Homomorphically长大次方 ,也就是说,

和计算

根据同态加密方案FH-SIMD,对应的密文明文的力量。当然,密文homomorphically的权力 ,通过执行2n应用乘法。因为相对应的明文是一个有限域的元素和马克斯乘法订单 ,然后相对应的明文要么是0或1。因此,是加密的密文1(非零元素)或加密的密文0(零元素)。当是一个加密的0,这意味着 持有;当是一个加密的1,这意味着 做没用的人。

计算

我们可以看到,只要方程 持有,我th组成部分是 ;否则,第i个组成部分是 。因此,如果有一个退出 这样 成立,那么 ,和所有其他 ,对所有 。由此可见, 。也就是说,如果有一个退出 这样 持有,阻止homomophic平等测试算法输出 ;否则输出 。

从上面的步骤,我们完成块同态平等测试;然后我们可以同态计算 ,也就是说, 。

3.3。更快的引导技术

在本节中,我们构造速度引导程序块的同态平等测试算法B_Eq ?。引导过程包含两个算法:BootKeyGen和引导。所有已知的过程是用来刷新暗文标准LWE-based FHE。我们得到输入密文 为引导,从减少dimension-modulus和bit-decomposition密文的引导。让 是对应的密钥密文

BootGen :输入密钥 密文的刷新和公钥pkFH-SIMD计划。不失一般性,对于每一个 ,编码每个坐标 有限域的元素 。FH-SIMD方案然后加密的密文,并生成引导的关键:

输出引导公共密钥 。引导键组成FH-SIMD暗文。

引导 :输入的二进制密文 ,并执行以下两个阶段:(我)内积Homomorphically计算内积使用引导公共密钥 。众所周知, 由此可见, (2)轮对于每一个 满足 ,安排订单的大小,划分成块项目,我们假设他们是截然不同的,完全有块: 每一块 ,运行测试块同态平等并行算法, 然后计算

我们可以看到,要么是或 ,然后是加密的 , 也不是或 ,它刷新密文较小的错误。注意,输出是一个FH-SIMD密文加密 。如果需要,我们可以将这个密文转换为一个原始LWE FHE密码系统。我们还可以执行钥匙开关回到原来的密钥。

4所示。分析

4.1。正确分析

引理1(正确性)。为 ,的FH-SIMD密文 设计加密 。

证明。首先,FH-SIMD密文设计加密从(18)。因此,自 同态嵌入,密文吗在(定义为20.加密) 块同态平等测试算法的正确性B_Eq吗?,同态的总和 1当且仅当设计加密 。最后,由于同态和每个接管 这样 ,它被设计为加密1当且仅当 。

4.2。安全分析

引理2(语义安全性)。假设FH-SIMD计划秘密密钥生成独立的密钥 从LWE FHE方案;然后Ind-CPA引导安全关键紧跟着FH-SIMD Ind-CPA安全的,因此从SIVP理想的晶格。

证明。为 ,如果没有敌人可以区分引导的关键从一个随机元素在同一个空间,然后引导过程称为satisfing语义安全。
在我们的引导过程, ,引导键组成FH-SIMD暗文;也就是说, 通过FH-SIMD生成方案,在哪里 假设有一个对手可以区分引导从随机元素。然后我们可以构造一个算法通过调用对手和打破Ind-CPA FH-SIMD方案和安全,此外,解决理想的SIVP晶格。

4.3。性能分析

我们的块同态平等测试算法B_Eq ?有一个成本 每个数据块表示的密文和添加操作表示乘法运算的密文,而同态平等测试算法情商?涉及到 ,B_Eq的指数倍吗?算法,也就是说,情商的计算?算法更昂贵,参考表1。

工作的Alperin-Sheriff和Peikert [11),一个内积评价引导需要计算暗文撰写评估,引导需要调用舍入的评价之一情商?算法,密文乘法操作。而我们内部的生产速度引导需要计算密文的增加,一个四舍五入评估需要调用B_Eq吗?算法,块的大小,块的数量, 。

假设LWE问题80位安全时设置为2003。参数设置如上所述,当设置为2003,2047,2501,3001,4093,到12899年,我们给乘法操作数量和模量之间的关系 ,如图3。随着模量q的增加,密文乘法操作数量的增长迅速在美联社的引导过程,而密文乘法操作数量的增长缓慢。

另一方面,固定模量和米乘法运算,给出了关系数量一旦运行更快的引导程序基于块的块大小同态平等测试算法B_Eq ?。当 , ,和 ,所以 ,我们设置 ,满足 。然后我们组块的大小 ,也就是说,块的大小 。那块的数量 。我们可以看到从图4随着块大小的增加,密文乘法操作急剧下降。

5。结论

完全同态加密方案允许评估加密数据,没有解密对应的密文。在完全同态加密方案中,密文有噪音,生长在每一个同态的评估。当噪声达到一个阈值,则无法正确解密密文。同态操作的数量可以渐近大使用引导技术。

在本文中,我们进一步研究了引导程序。我们提出的概念块同态平等测试算法基于FH-SIMD方案并给出一个实例。此外,我们提供更快的引导过程基于块同态平等测试算法。理论分析和实验仿真验证我们的引导比这更高的性能的工作(11]。

数据可用性

我们的基础数据与这篇文章相关的论文引用如(11]。

的利益冲突

作者宣称他们没有利益冲突有关的出版。

确认

这项工作是由中国国家自然科学基金支持下批准号61601515和河南省自然科学基金批准号162300410332。

引用

1. c .绅士”完全同态加密使用理想的晶格,”Proc的进球数年度美国电脑计算理论(获得STOC),“ACM,第178 - 169页。纽约,纽约,美国,2009年。视图:谷歌学术搜索
2. c .绅士一个完全homomophic加密方案(博士学位。论文)斯坦福大学,2009年,http://crypto.stanford.edu/craig。
3. z Brakerski和诉Vaikuntanathan高效完全同态加密(标准)LWE”《IEEE 52年度研讨会上计算机科学的基础(foc 11)棕榈泉,页97 - 106年,加州,美国,2011年10月。视图:出版商的网站|谷歌学术搜索
4. z Brakerski诉Vaikuntanathan,“从ring-LWE完全同态加密和安全关键依赖信息,”2011年Cryptology-CRYPTO进步卷,r·菲利普·艾德。6841年,页505 - 524,施普林格,柏林,德国,2011年。视图:出版商的网站|谷歌学术搜索|MathSciNet
5. m·冯·c .绅士s Halevi诉Vaikuntanathan,“在整数,完全同态加密”密码学的发展(EUROCRYPT)卷,6110,pp。24-43,施普林格,柏林,德国,2010年。视图:出版商的网站|谷歌学术搜索|MathSciNet
6. 鲲鹏辅罗Fuqun Wang Wang杰,陈和文雅,“LWR-Based完全同态加密,再现。”安全性和通信网络卷,2018篇文章ID 5967635, 12页,2018。视图:出版商的网站|谷歌学术搜索
7. n . p .聪明和f·“完全同态SIMD操作,”设计、编码和加密,卷71,不。1,57 - 81,2014页。视图:出版商的网站|谷歌学术搜索
8. c .绅士,a . Sahai和水域,“同态加密从学习错误:conceputally-simpler, asymptotically-faster,属性,”加密,信号,r . Canetti和j . a .浏览完。,卷。8042,pp. 75–92, Springer, Heidelberg, Germany, 2013.视图:谷歌学术搜索
9. c .绅士美国Halevi, n . p .聪明,“在完全同态加密,更好的引导”公钥密码术(PKC)卷,7293课堂讲稿的第一版。科学。施普林格,页1 - 16,海德堡,2012年。视图:出版商的网站|谷歌学术搜索|MathSciNet
10. j . Alperin-Sheriff和c . Peikert”实际引导拟线性时间,”密码学的发展——加密卷,8042年,页1 - 2013。视图:出版商的网站|谷歌学术搜索|MathSciNet
11. j . Alperin-Sheriff和c . Peikert“速度与多项式错误引导,”《国际密码学会议、j . a .浏览完和r .热内罗Eds。,pp. 297–314, Springer, Berlin, Germany, 2014.视图:出版商的网站|谷歌学术搜索|MathSciNet
12. l . Ducas和d . Micciancio FHEW:引导同态加密在不到一秒,”EUROCRYPT,第一部分,信号奥斯瓦尔德和m . Fischlin Eds。,卷。9056,pp. 617–640, Springer, Heidelberg, Germany, 2015.视图:谷歌学术搜索
13. Georgieva i Chillotti:伽马,m . et al .,“快完全同态加密:引导在不到0.1秒,”密码学的发展——ASIACRYPT页,3-33施普林格,德国海德堡2016。视图:出版商的网站|谷歌学术搜索
14. Georgieva i Chillotti:伽马,m . et al .,“快满同态操作和有效的电路TFHE向导功能,”ASIACRYPT 2017。信号高木涉和t . t . Peyrin Eds。,卷。10624,pp. 377–408, Springer, Cham, UK, 2017.视图:谷歌学术搜索
15. w·t·周x, l . Liu, n .李,“更快的引导与多个叫做加数,”IEEE访问》第六卷,第49876 - 49868页,2018年。视图:出版商的网站|谷歌学术搜索

版权

版权©2018秀峰赵和Ailan王。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。