古春生，景征駿，于志敏

1.江蘇技術師范學院計算機工程學院，江蘇常州 213001

2.中國科學技術大學計算機科學與技術學院，合肥 230027

3.南京郵電大學計算機學院，南京 210003

破解較快速的整數(shù)上的全同態(tài)加密方案

古春生1，2，景征駿1，3，于志敏1

1.江蘇技術師范學院計算機工程學院，江蘇常州 213001

2.中國科學技術大學計算機科學與技術學院，合肥 230027

3.南京郵電大學計算機學院，南京 210003

1 前言

1978年，Rivest，Adleman和Dertouzos[1]提出了下面非常有趣的問題，即沒有解密密文并且一直保持加密狀態(tài)，是否能對密文中數(shù)據(jù)進行任意計算?這就相當于在沒有看到數(shù)據(jù)情況下，在加密數(shù)據(jù)上進行計算。這種能力也有許多實際應用，如在云計算平臺上，客戶儲存所有加密數(shù)據(jù)到云中，在加密數(shù)據(jù)上實行計算，僅將云計算平臺中的計算結果以密文形式返回給客戶，并在客戶端進行解密。

直到2009年，Gentry[2]才第一次構造出基于理想格問題全同態(tài)加密方案。在Gentry方案以后，全同態(tài)加密立即成為當前密碼研究熱點之一。在2010年，Smart和Vercauteren[3]使用主理想格優(yōu)化設計了一個全同態(tài)加密方案，該方案具有更小的密文和密鑰。Dijk，Gentry，Halevi和Vaikuntanathan[4]基于近似整數(shù)GCD問題構造了一個概念上更簡單的整數(shù)上全同態(tài)加密方案。Stehle和Steinfeld[5]改進Gentry方案成為一個更快的全同態(tài)加密方案。在2011年，類似于文獻[3]， Gentry和Halevi[6]實際實現(xiàn)了基于理想格Gentry的全同態(tài)加密方案。文獻[7]改進了文獻[4]中基于整數(shù)上近似最大公因式問題（AGCD）的全同態(tài)加密方案，并在方案中應用了文獻[5]中的“可忽略概率解密錯誤”的思想。

本文工作主要集中于分析文獻[7]中全同態(tài)加密方案的安全性。針對文獻[7]中方案，本文使用方案公鑰和密文構造一個低維格，然后調用LLL算法[8]直接求出加密時選擇的兩個隨機數(shù)，從而獲得密文中的明文比特。因此，本文破解了文獻[7]中的全同態(tài)加密方案。

2 文獻[7]的全同態(tài)加密方案

為了敘述簡單，本文直接使用文獻[7]中符號和約定。因為Somewhat同態(tài)加密方案是全同態(tài)加密方案基礎組成部分，即如果破解了Somewhat同態(tài)加密方案，則基于Somewhat方案構造的全同態(tài)方案也就破解了。由于本文主要是直接攻擊Somewhat同態(tài)加密方案，因而這里將僅引用文獻[7]中Somewhat同態(tài)加密方案。為節(jié)省空間，文獻[7]中全同態(tài)加密方案這里略去。

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

參數(shù)選取：設λ為安全參數(shù)，ρ=λ，ρ′=2λ，η=O~(λ2)，θ=λ4，γ=O~(λ5)。

密鑰產生算法（KeyGen）：隨機選擇η比特的奇素數(shù)p 和θ比特的奇素數(shù)q，計算N=pq。然后選取兩個隨機整數(shù)l∈[0，2γ/p]，h∈(-2ρ，2ρ)，計算x=pl+2h。輸出公鑰pk= (N，x)，私鑰sk=p。

加密算法（Enc）：給定消息比特m∈{0，1}和公鑰pk= (N，x)，選擇兩個隨機整數(shù)r1∈(-2ρ′，2ρ′)和r2∈(-2ρ，2ρ)，計算輸出密文c=(m+2r1+r2x)modN。

解密算法（Dec）：給定密文c和私鑰sk=p，計算輸出明文比特m=[c]pmod2。

注意符號[c]p表示cmodp并取絕對最小剩余，即[c]p∈(-p/2，p/2]。假定本文中一般模運算都取值為非負最小剩余。

對于適當選取的參數(shù)，不難驗證上述公鑰方案能夠實行密文的加法和乘法操作。具體情況見文獻[4，7]。

3 格攻擊算法

格攻擊基本思想：注意到在Somewhat同態(tài)加密方案中，盡管公鑰pk=(N，x)中x的比特長度很大，但N中并不包含噪聲因子。故在x中減去N的任意倍數(shù)并不改變其是比特“0”的密文。在加密算法Enc中對密文取模N也說明了這一點。因此本文利用這一性質通過公鑰和密文構造一個低維（這里是3）的格，使得格中最短向量就是加密時所選取的隨機值。而對于低維格，LLL算法[8]通常能夠求得格的最短向量。從而破解了文獻[7]中的全同態(tài)加密方案。

對于Somewhat同態(tài)加密方案，易于證明下面兩個觀察。

觀察1：假定y=xmodN，則c=(m+2r1+r2x)modN= (m+2r1+r2y)modN。

觀察2：假定y=xmodN，則c=(m+2r1+r2x)modN= R1+R2y+R3N，且Ri∈(-2ρ′+1，2ρ′+1]，i=1，2，3，這里R1=m+ 2r1，R2=r2。

基于觀察1，2，構造以行向量為基的格L如下：

盡管上述觀察1，2很顯然，證明也容易，但卻是格攻擊文獻[7]中全同態(tài)加密方案的關鍵。因為如果在格L中使用x，而不用y，則不能夠保證其最短向量為滿足上述條件的向量R=(R1，R2，R3)。

因此，使用上述構造的格和調用多項式時間的LLL算法，本文破解了文獻[7]中整數(shù)上的全同態(tài)加密方案。

4 攻擊實驗

本文格攻擊實驗使用NΤL庫[10]。攻擊實驗如下所述。

4.1 攻擊過程演示

攻擊演示示例選擇參數(shù)為：λ=6，ρ=λ，ρ′=2λ，η=2λ2，θ=λ4，γ=2λ5。其他參數(shù)具體取值如下：

由密文和公鑰構造的格L為：

對格L調用LLL算法后輸出的歸約基為：

易于驗證向量R=[R1，R2，R3]=[-6 8859-8]=[2r1+ 1，r2，R3]。因此，可以判定密文中明文比特為“1”，即可以根據(jù)R1的奇偶性來判定密文中包含的明文比特。

4.2 實用參數(shù)攻擊實驗

計算攻擊實用參數(shù)實驗數(shù)據(jù)如表1所示，對于參數(shù)p，q，n，x，y，表1中數(shù)字指其比特長度，其他參數(shù)為實際數(shù)值。由表1中實驗數(shù)據(jù)可以看出攻擊100%成功，因此文獻[7]中全同態(tài)加密方案是不安全的。

5 結束語

本文研究分析文獻[7]中較快速的全同態(tài)加密方案的安全性。針對文獻[7]中方案，本文使用方案公鑰和密文構造一個維數(shù)為3的格，然后直接調用LLL算法[8]求出加密時隨機選擇的兩個隨機數(shù)，進而獲得密文中所包含的明文比特。最后通過計算實驗攻擊，驗證了本文格攻擊方法的正確性和有效性。因此，本文破解了文獻[7]中較快速的全同態(tài)加密方案。

表1 格攻擊全同態(tài)加密方案的計算實驗數(shù)據(jù)表

[1]Rivest R，Adleman L，Dertouzos M.On data banks and privacy homomorphisms[C]//Foundations of Secure Computation，1978：169-180.

[2]Gentry C.Fully homomorphic encryption using ideal lattices[C]// SΤOC 2009，2009：169-178.

[3]Smart N P，Vercauteren F.Fully homomorphic encryption with relatively small key and ciphertext sizes[C]//LNCS 6056：Public Key Cryptography-PKC 2010，2010：420-443.

[4]van Dijk M，Gentry C，Halevi S，et al.Fully homomorphic encryption over the integers[C]//LNCS 6110：Eurocrypt 2010， 2010：24-43.

[5]Stehle D，Steinfeld R.Faster fully homomorphic encryption[C]// LNCS 6477：Asiacrypt 2010，2010：377-394.

[6]Gentry C，Halevi S.Implementing Gentry’s fully-homomorphic encryption scheme[C]//LNCS 6632：Eurocrypt 2011，2011：129-148.

[7]湯殿華，祝世雄，曹云飛.一個較快速的整數(shù)上的全同態(tài)加密方案[J].計算機工程與應用，2012，48（28）：117-122.

[8]Lenstra H W，Lenstra A K，Lovasz L.Factoring polynomials with rational coefficients[J].Mathematische Annalen，1982，261：515-534.

[9]Nguyen P Q，Vallée B.Τhe LLL algorithm：survey and applications[M]//Information Security and Cryptography.[S.l.]：Springer，2009：33-35.

[10]Shoup V.NΤL：a library for doing number theory[EB/OL]. [2011-11-20].http：//shoup.net/ntl/.

GU Chunsheng1，2,JING Zhengjun1，3,YU Zhimin1

1.School of Computer Engineering,Jiangsu Τeachers University of Τechnology,Changzhou,Jiangsu 213001,China
2.School of Computer Science and Τechnology,University of Science and Τechnology of China,Hefei 230027,China
3.School of Computer Science,Nanjing University of Posts and Τelecommunications,Nanjing 210003,China

It is very important to analyze the security of optimizing fully homomorphic encryption scheme.For the fully homomorphic encryption scheme designed by Τang et al.,this paper directly obtains the plaintext bit from a ciphertext by applying lattice reduction attack.Τhus,this faster fully homomorphic encryption scheme is broken.

fully homomorphic encryption;approximate Greatest Common Divisor（GCD）;cryptanalysis;lattice reduction attack

研究分析優(yōu)化的全同態(tài)加密方案的安全性十分重要。針對湯等人設計的全同態(tài)加密方案，使用格歸約攻擊方法直接獲取密文中的明文比特，從而破解了該較快速的全同態(tài)加密方案。

全同態(tài)加密；近似最大公約數(shù)（GCD）問題；密碼分析；格歸約攻擊

A

ΤN918.4

10.3778/j.issn.1002-8331.1201-0401

GU Chunsheng,JING Zhengjun,YU Zhimin.Breaking faster fully homomorphic encryption scheme over integer.Computer Engineering and Applications,2013,49（21）：101-105.

國家自然科學基金（No.70671096）；江蘇技術師范學院基金（No.KYY11055）。

古春生（1971—），男，博士，副教授，研究方向：密碼分析；景征駿（1974—），男，博士生，講師；于志敏（1974—），男，講師。E-mail：guchunsheng@gmail.com

2012-01-30

2012-03-13

1002-8331（2013）21-0101-05

CNKI出版日期：2012-06-01http://www.cnki.net/kcms/detail/11.2127.ΤP.20120601.1456.003.html