循環安全的同態加密方案

趙秀鳳 付 雨 宋巍濤

(信息工程大學密碼工程學院 鄭州 450001)

當今世界，大數據、云計算等蓬勃發展，使互聯網時代邁上一個新臺階.然而，云計算和大數據所具有的數據集中、資源共享、高度互聯、全面開放等特點，一方面打破了傳統IT領域的信息孤島，另一方面也帶來了更嚴峻的安全問題.云計算模式的核心是數據，本質是服務，特點是“零信任”，因此，“數據在不可信環境下的安全計算(服務)”成為解決云計算安全的一個關鍵問題.2009年IBM實驗室的Gentry首次給出了“全同態加密”(fully homomor-phic encryption, FHE)方案[1-2].全同態加密可以在不解密的情況下對密態數據進行各種運算，其結果在解密后與對明文進行相應運算的結果是一樣的.全同態加密不僅能夠對密文進行任意的盲操作，而且還能夠對計算操作行為本身進行加密的密碼算法，因此，全同態加密真正從根本上解決了將數據及操作委托給第三方時的保密問題，使人們既可以充分利用云計算強大的計算和存儲能力為用戶提供海量密文處理服務，又可以自己管理保證數據安全的密鑰，實現了“數據在不可信環境下安全計算(服務)”.

本文的主要貢獻包括2個方面:

1) 給出了滿足循環安全性的公鑰同態加密方案，并給出了安全性證明和參數設置分析；

2) 通過引入拒絕采樣技術，對上述滿足循環安全性的同態加密方案進行了優化，將方案參數從超多項式級降低到多項式級，大大約減了參數規模，有效提升了方案的效率.

1 相關工作

關于循環安全的加密方案已有一些研究成果.Boneh等人基于無隨機Oracle的DDH假設構造了一個循環安全的公鑰加密方案[3].Applebaum等人根據基于錯誤學習(learning with error, LWE)問題的Regev加密方案[4]，構造了循環安全的有效密碼體制[5].在循環安全的同態加密方面，楊曉元等人[6]基于LWE問題的變形給出了一個對私鑰的線性函數滿足循環安全的FHE方案，但是這個困難假設并不是一個標準的困難假設.Zhao等人[7]給出了矩陣GSW方案[8]滿足循環安全性的一個充分條件，但是缺乏必要性證明.2011年美國密碼學年會，Brakerski和Vaikuntanathan[9]基于環LWE問題給出了一個循環安全的同態加密方案，稱為BV方案.BV方案實現循環安全性的基本思路是利用“噪聲淹沒技術”(noise flooding technique)，即在原加密方案的基礎上，再引入一個“寬高斯”分布的噪聲，從而使得對密鑰加密的密文與對普通明文加密的密文不可區分.由高斯分布的疊加性和不可區分性，保證挑戰者模擬私鑰的密文.

本文給出的循環安全的公鑰同態加密方案，通過引入拒絕采樣技術有效約減了密文模的規模，提升了同態運算的效率.該研究成果可以為同態加密方案設計與實現提供理論參考.

2 基礎知識

本節主要介紹本文用到的基本定義和重要的引理.

2.1 離散高斯分布

標準方差為σ、中心為c的高斯分布定義為

對于?x,c∈Rn,離散高斯的分布概率密文函數定義為

Z和Zn上的離散高斯分別定義為

引理3[12].令n∈N,m=2n,f(x)=xn+1,令R=Z[x](f(x)).對于任意的s,t∈R,

特別地，當n=1,r=6時，有:

引理5[14].令λ為安全參數.Φm(x)=xn+1是度為n=φ(m)=m2的m次分圓多項式.令σ≥為一個實數，q≡1(modm)為素數.令R=Z[x]Φm(x),則存在一個從2ω(log n)×(qσ)-近似R-SVP問題到RLWEΦm,q,χ的隨機歸約算法，其中，χ=DZn,σ為離散高斯分布.歸約算法的運行時間為poly(n,q).

2.2 拒絕采樣

拒絕采樣技術由Neumann提出，給出了通過源概率分布采樣得到目標概率分布采樣的一個方法[15].PKC2008，Lyubashevsky利用拒絕采樣構造了基于格的身份識別協議[16].Crypt2013，Ducas等人利用拒絕采樣構造了基于格的BLISS數字簽名算法[17].NIST征集的多數后量子數字簽名候選算法也采用了拒絕采樣技術.

引理6.拒絕采樣.令V是任意一個集合，h:V→R和f:Zm→R為概率分布.若gv是以v為索引的一簇概率分布，并且存在一個M∈R，使得:

?v∈V,?z∈Zm,M.gv(z)≥f(z),

那么，2個算法輸出的分布是相同的：

1)v←h,z←gv,以概率f(z)(M.gv(z))輸出(z,v)；

2)v←h,z←f,以概率1M輸出(z,v).

2.3 同態加密的循環安全性定義

1) 挑戰者計算(pk,sk,evk)←KeyGen(λ),并隨機選擇一位b←{0,1}；

在基于LWE的FHE方案中，Evalevk(f+,Encpk(0),f(sk))可以視為加密f(sk)的密文.

3 循環安全的公鑰同態加密方案

為了實現對私鑰sk的多項式p(sk)的KDM安全性，我們利用對稱版本的方法，將標準的同態加密的密文(c0,c1)擴展為(c0,c1,…,cd)，其中d為多項式p(sk)的度.我們令d=2,即我們考慮對私鑰sk的平方函數滿足循環安全性的同態加密方案，記作KDM.PKHE.

3.1 方案描述

具體算法描述為：

2) KDM.PKHE.Keygen(1λ).隨機選擇a0∈Rq，從離散高斯分布采樣得到s,e0←DZn,σ，計算b0=a0s+te0，輸出私鑰sk=s和公鑰pk=(a0,b0).

故上述無窮范數小于q2時,則可以解密成功.

3.2 循環安全性證明

為了給出KDM.PKHE方案的循環安全性證明，我們首先證明引理：

引理7.設ξ和η是Zq上2個獨立的隨機變量，且ξ在Zq上服從均勻分布，那么ξ+η在Zq上也服從均勻分布.

證明. 設ξ和η獨立，則?z∈Zq,有:

由ξ在Zq上服從均勻分布知:

因此有:

即ξ+η在Zq上服從均勻分布.

證畢.

證畢.

實驗G0. 實驗G0是真實的KDM-CPA安全實驗，如2.3節定義中所述.在該實驗中，挑戰者按照加密算法生成挑戰密文

實驗G1. 除了挑戰密文的生成方式不同之外，實驗G1和G0相同.實驗G1中，挑戰者按照2種方式生成f(sk)的挑戰密文：

當b=0時，設置挑戰密文為

當b=1時，設置挑戰密文為

(c0=b1+0,c1=b2-a1,c2=-a2).

證畢.

(1)

證明. 對于消息s2∈Rt，考察同態加密方案的密文c0：

(2)

令Δ=2n1.5σ2，由σ′=2ω(log n)σ2，有:

另外，考察同態加密方案的密文c1：

(3)

因此，敵手區分實驗G1和G0的概率是忽略的，引理8成立.

實驗G2：除了挑戰密文的生成方式不同之外，實驗G2和G2相同.實驗G2中，挑戰者按照2種方式生成f(sk)的挑戰密文：

當b=0時，設置挑戰密文為

當b=1時，設置挑戰密文為

(c0=b1+0,c1=b2-a1,c2=-a2).

其中，ui(i=0,1,2)為環Rq中的隨機元素.

證畢.

(4)

綜上，有：

由于在實驗G2中，挑戰密文是與私鑰s獨立的均勻隨機的環元素，因此敵手的優勢是可忽略的，即：

(5)

綜合式(1)(4)(5)，有:

至此，我們證明了敵手的KDM安全性實驗中的優勢是可忽略的.

證畢.

3.3 參數設置

KDM.PKHE方案中的參數并不是獨立選擇的，相互之間存在一些制約關系,下面給出詳細分析.

1) 為了使得離散高斯分布DZn,σ′可以“淹沒”DZn,σ上采樣的2次多項式，要求σ′=2ω(log n)σ2.

故密文模q滿足q>t×2ω(log n)×σ2可保證解密正確性.

4 改進方案

為了利用噪聲淹沒技術實現循環安全性，離散高斯分布DZn,σ′的標準方差σ′需要滿足σ′=2ω(log n)σ2，而解密正確性要求模數q>t×2ω(log n)×σ2，因此，模數q是n的超多項式函數，使得KDM.PKHE方案的效率極低.下面，我們以d=2這種情況為例，通過引入拒絕采樣技術來約減σ′的規模，進而降低q的規模，并最終提高循環安全的KDM.PKHE方案效率.

4.1 方案描述

除了加密算法中噪聲采樣算法不同之外，改進方案同KDM.PKHE方案基本相同，記為RS.KDM.PKHE.

2) RS.KDM.PKHE.Keygen(1λ).隨機選擇a0∈Rq，從離散高斯分布采樣得到s,e0←DZn,σ，計算b0=a0s+te0，輸出私鑰sk=s和鑰pk=(a0,b0).

① 計算ai=a0vi+tei，其中vi,ei←DZn,σ.

③ 計算對m加密后的密文：

c0=b1+m;
c1=b2-a1;
c2=-a2.

4.2 方案正確性分析

如圖1所示(n=1的情形)，我們令拒絕采樣的目標概率分布是DZn,σ′，源概率分布是DZn,σ′,Ei.為了利用拒絕采樣技術，我們需要找到實數M，使得對于所有的x∈Zn,有DZn,σ′(x)≤M×DZn,σ′,Ei(x).根據高斯分布的定義有：

Fig. 1 Reject sampling technique圖1 拒絕采樣技術

4.3 方案性能分析

通過第2節分析可知，只要設置σ′=τ×Δ=2τn1.5σ2，即可以利用拒絕采樣技術完成加密過程.如表1所示，RS.KDM.PKHE方案中σ′從BV的KDM.SKHE和KDM.PKHE方案中σ2的超多項式倍2ω(log n)×σ2降低為σ2的多項式倍poly(n)×σ2,大大約減了的σ′的規模.根據解密正確性要求，密文模數q的規模從2ω(log n)×σ2×t降低到poly(n)×σ2×t，有效約減了密文規模，提升了同態運算的效率.

Table 1 Parameter Setting表1 參數設置

4.4 循環安全的公鑰同態加密方案

2) KDM.KeyGen(1λ).隨機選擇a0∈Rq，從離散高斯分布采樣得到s,e0←DZn,σ，計算b0=a0s+te0，輸出私鑰sk=s和公鑰pk=(a0,b0).

① 計算ai=a0vi+tei，其中vi,ei←DZn,σ.

③ 計算對m加密后的密文：

c0=b1+m,
ci=bi+1-ai,i=1,2,…,d-1,
cd=-ad.

m=c,smodt.

5 結束語

本文基于噪聲淹沒技術給出了循環安全的公鑰同態加密方案，并給出了安全性證明和參數設置.進一步，首次將拒絕采樣技術引入到循環安全的同態加密方案構造方法中，給出了優化的循環安全公鑰加密方案，使得系統參數從超多項式級降低到多項式級，有效約減了公鑰規模和密文規模.

另一方面，由于拒絕采樣技術的應用，導致加密算法的計算復雜性增加，但是考慮到同態加密方案的瓶頸在于密文運算，而不是新鮮密文的生成算法，而我們的方案將密文規模從超多項式級降低到多項式級，因此，可以有效降低密文運算的計算復雜性.總體而言，基于拒絕采樣技術構造的循環安全性同態加密方案具有良好的性能.