◆李凱強 高亞斌 于曉昆 姚 悅

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

◆李凱強 高亞斌 于曉昆 姚 悅

（國網電子商務有限公司 英大商務服務有限公司 天津 300309）

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

同態(tài)加密最初由Rivest等人[1]在1978年創(chuàng)造性提出的，其創(chuàng)造性在于能對密文進行操作，對解密后的密文進行解密得到直接操作明文的結果?；诖颂匦圆⒔Y合云強大的計算能力，可以在云端操作密文來保證云端數據的安全，從而有著廣闊的運用場景及空間[2]。

1 相關基礎定義

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

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

1.3 定義3（擴展的解密電路）

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

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

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

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

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

2.2.1新方案描述

其中

得出：

Decrypt（，）：

2.2.2新方案的正確性論證

由定義4可得

故

根據定義5可知新構造的方案的正確性得到了保證。

2.2.3新方案安全性論證

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

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

2.3.1壓縮解密電路

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

2.3.2解密正確性證明

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

所以

2.3.3自舉性

3 新方案效率分析

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

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

4 結束語

[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]林如磊，王箭，杜賀.整數上的全同態(tài)加密方案的改進[J].計算機應用研究，2013，30（5）：113-122.

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

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

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

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

[13]熊婉君，韋永壯，王會勇.一個基于整數的全同態(tài)加密改進方案[J].密碼學報，2016（01）：67-78.