一個(gè)基于整數(shù)的高效全同態(tài)加密方案

◆李凱強(qiáng) 高亞斌 于曉昆 姚 悅

一個(gè)基于整數(shù)的高效全同態(tài)加密方案

◆李凱強(qiáng) 高亞斌 于曉昆 姚 悅

（國網(wǎng)電子商務(wù)有限公司 英大商務(wù)服務(wù)有限公司 天津 300309）

全同態(tài)加密；近似最大公約數(shù)問題; 稀疏子集和問題；二次形式

同態(tài)加密最初由Rivest等人[1]在1978年創(chuàng)造性提出的，其創(chuàng)造性在于能對(duì)密文進(jìn)行操作，對(duì)解密后的密文進(jìn)行解密得到直接操作明文的結(jié)果。基于此特性并結(jié)合云強(qiáng)大的計(jì)算能力，可以在云端操作密文來保證云端數(shù)據(jù)的安全，從而有著廣闊的運(yùn)用場(chǎng)景及空間[2]。

1 相關(guān)基礎(chǔ)定義

1.1 定義1（同態(tài)加密）

1.2 定義2（解密的正確性（））

1.3 定義3（擴(kuò)展的解密電路）

1.4 定義4（同態(tài)的加密方案）

2 一個(gè)基于整數(shù)的高效全同態(tài)加密方案

2.1 全同態(tài)加密方案的設(shè)計(jì)思路

本文按照Gentry壓縮解密電路的方法，第一步構(gòu)造一個(gè)能夠進(jìn)行有限次加以及乘運(yùn)算的Somewhat同態(tài)加密體制。第二步根據(jù) “壓縮”解密電路的方法，通過引進(jìn)SSSP問題假設(shè)，以及加法或乘法門的電路構(gòu)造（擴(kuò)展）解密電路，獲得體制的全同態(tài)。

2.2 新Somewhat同態(tài)加密方案

2.2.1新方案描述

其中

得出：

Decrypt（，）：

2.2.2新方案的正確性論證

由定義4可得

故

根據(jù)定義5可知新構(gòu)造的方案的正確性得到了保證。

2.2.3新方案安全性論證

定義6基于無錯(cuò)的近似最大公約數(shù)問題[6]（Error ?Free AGCD）

2.3 全同態(tài)加密方案的設(shè)計(jì)

2.3.1壓縮解密電路

式（1）的證明過程如下：

2.3.2解密正確性證明

由式2.3.1中對(duì)式（1）的論證可得，原式=

所以

2.3.3自舉性

3 新方案效率分析

表3 比較Somewhat同態(tài)加密方案

表4 比較全同態(tài)加密方案

4 結(jié)束語

[1]Rivest R，Adleman L，Dertouzos M. On data banks and privacy homomorphisms [J]. Foundation of Secure Computation， 1978：160-171.

[2]Onomza WV.Big data analytics and data security in the cloud viafully homomorphic encryption[J].International Journal of Computer and Information Engineering，2015，9（5）：744-753.

[3]Gentry C.Fully homomorphic encryption using ideal lattices [C]//Proc of the 41st Annual ACM Symposium on Theory of Computing. 2009：169-178.

[4]GENTRY C.A fully homomorphic encryption scheme [D].Stanford：Stanford University，2009．

[5]Van Dijkm G，Halevis. Fully homomorphic encryption over the integers[C]//Advances in Cryptology-EUROCRYPT. Berlin：Springer，2010：118-130.

[6]Cronj S，Mandala N. Fully homomorphic encryption over the integers with shorter public keys[C]//Advances in Cryptology-CRYPTO. Berlin：Springer，2011：94-145.

[7]CORON J S，NACCACHE D，TIBOUCHI M. Public key compression and modulus switching for fully homomorphic encryption over the integers[C] //Advances in Cryptology-EUROCRYPT. Berlin：Springer，2012：446-464．

[8]林如磊，王箭，杜賀.整數(shù)上的全同態(tài)加密方案的改進(jìn)[J].計(jì)算機(jī)應(yīng)用研究，2013，30（5）：113-122.

[9]李子臣，張峰娟，王培東.一種短密鑰高效全同態(tài)加密方案[J].計(jì)算機(jī)應(yīng)用研究，2017（02）：1-4.

[10]孫霓剛，朱浩然，汪偉昕.一種適用于n bit的整數(shù)上全同態(tài)加密方案[J].計(jì)算機(jī)應(yīng)用研究，2018，35（04）：1179-1181.

[11]代洪艷，丁勇，呂海峰，高雯.一種較快速的基于整數(shù)的全同態(tài)加密方案[J].計(jì)算機(jī)應(yīng)用研究，2015（11）：3448-3451+3455.

[12]羅炳聰，柳青，馬遠(yuǎn)，等.具有較短公鑰的批處理整數(shù)上的全同態(tài)加密[J].計(jì)算機(jī)應(yīng)用研究，2014，31（4）：1180-1184.

[13]熊婉君，韋永壯，王會(huì)勇.一個(gè)基于整數(shù)的全同態(tài)加密改進(jìn)方案[J].密碼學(xué)報(bào)，2016（01）：67-78.