李習習, 唐春明, 胡業(yè)周

廣州大學數(shù)學與信息科學學院, 廣州 510006

1 引言

云存儲與云計算平臺的快速發(fā)展使用戶可以外包存儲、計算自身的數(shù)據(jù), 這樣用戶就能夠節(jié)省投資費用, 簡化復雜的設置和管理任務. 然而, 私密信息、有價值的商業(yè)數(shù)據(jù)泄露成為其發(fā)展的一大障礙. 全同態(tài)加密(full homomorphic encryption, FHE) 的出現(xiàn)為上述問題提供了一個很好的解決方案, 全同態(tài)加密的一個顯著特征就是允許任何人對密文直接進行計算操作, 解密結(jié)果相當于對明文做同樣的計算操作, 即dec(f(Enc(m1),Enc(m2),··· ,Enc(mn)))=f(m1,m2,··· ,mn).

傳統(tǒng)的全同態(tài)加密體制對單個用戶的單個比特進行加密, 無法實現(xiàn)一次加密多個比特以及對多個用戶上傳到云端的數(shù)據(jù)進行安全的多方聯(lián)合計算. 例如, 他們可能希望云來計算他們數(shù)據(jù)庫上的聯(lián)合統(tǒng)計信息;在數(shù)據(jù)庫集合中定位公共文件; 將多個(相互不信任的) 用戶的數(shù)據(jù)集中在一起, 通過特定的計算以實現(xiàn)共同的目標、達成統(tǒng)一的決策(除此之外不泄露其它隱私信息) 等. 在本文中, 我們設計一種支持多比特多密鑰的全同態(tài)加密方案, 使得多個用戶可以安全聯(lián)合計算目標數(shù)據(jù)的同時可以一次加密多個比特.

本文第2 節(jié)為綜述相關(guān)工作; 第3 節(jié)給出符號說明以及一些與本文相關(guān)的定義定理等; 第4 節(jié)簡要敘述我們的多比特全同態(tài)加密方案和該方案的安全性證明; 第5 節(jié)給出如何將多比特單密鑰密文擴展成多比特多密鑰密文; 第6 節(jié)給出我們的多比特多密鑰全同態(tài)加密方案并且證明了密文擴展的的正確性; 第7 節(jié)總結(jié)全文.

2 相關(guān)工作

全同態(tài)加密的思想最早由Rivest 等人[1]于1978 年提出, 如何構(gòu)造滿足全同態(tài)性質(zhì)的體制一直是困擾密碼學家的難題, 直到2009 年Gentry 基于理想格提出來第一個全同態(tài)加密體制[2], 隨后很多密碼學家在全同態(tài)加密體制的研究取得進展. 2010 年Smart 等人[3]在PKC 上簡化了Gentry09 體制的實現(xiàn).2011 年Gentry 等人[4]對Gentry09 體制做進一步的簡化, 并提出了部分同態(tài)加密方案的新的密鑰生成算法, 減少密鑰和密文長度, 使得部分參數(shù)的實現(xiàn)成為可能. 同年, Brakerski 等人基于LWE 提出了全同態(tài)加密方案[5], 但是他們的方案不能夠利用自舉以達到全同態(tài)的目的. 2012 年, Brakerski 又提出了一個基于LWE 的無需模數(shù)轉(zhuǎn)換管理噪音也能很好的控制噪音增長的全同態(tài)加密方案[6]. 但上述方案都需要“計算密鑰” 的輔助信息才能達到全同態(tài)的目的, 計算密鑰的尺寸都很大, 是制約全同態(tài)加密效率的一大瓶頸. 2013 年Gentry 等人利用“近似特征向量” 技術(shù), 設計了一個無需計算密鑰的全同態(tài)加密方案[7], 掀起了全同態(tài)加密研究的一個新高潮. 此后, 研究人員在高效的自舉算法、多密鑰全同態(tài)加密方案等方面進行了大量的研究.

2016 年, Gama 等人提出了一個更高效的自舉算法[8]: 運行一次自舉算法累積的噪音的上界是線性的. López-Alt 等人最先開始研究多密鑰全同態(tài)加密[9], 但是, 他們的方案用到了一個非標準的假設, 并且近年來也遭受到比較嚴重的攻擊. 所以設計安全的多密鑰全同態(tài)加密引起了人們的注意, 并研究出多個多密鑰全同態(tài)加密[10–13]. 在文獻[10] 與文獻[14] 中, 將一個密文矩陣(Expand) 操作, 產(chǎn)生一個新的密文,并將密鑰級聯(lián)成組合密鑰, 用組合密鑰解密擴展后的密文可以得到正確的解密結(jié)構(gòu), 而且多密鑰全同態(tài)加密方案的密文會隨著不同的密鑰數(shù)的增長而膨脹, 同態(tài)計算后的密文不能繼續(xù)執(zhí)行同態(tài)運算. 以上都是對單比特明文進行全同態(tài)加密, 而全同態(tài)加密方案一個最重要的問題就是效率問題, 單個比特的加密使得同態(tài)操作的效率很低, 為了提高全同態(tài)加密的計算效率, 人們提出了“密文打包” 的方法[15], 即將多個明文裝入到一個密文中. 該方法使得對密文執(zhí)行一次同態(tài)操作, 相當于并行對多個明文執(zhí)行同樣的操作. 本文基于2017 年李增鵬等人發(fā)表的基于Dual.LWE 多比特層次型全同態(tài)加密方案[16], 通過修改其加密算法使之成為無CRS 模型多比特全同態(tài)加密方案. 利用LinkAlgo 算法[17]對其密文進行密文擴展操作形成一個新的密文(多密鑰密文), 從而設計出一種支持多比特多密鑰全同態(tài)加密方案.

3 符號說明

4 MBGSW 方案

4.1 MBGSW 方案的正

4.2 MBGSW 方案安全性

5 用LinkAlgo 算法將上述多比特單密鑰密文擴展成多比特多密鑰密文

矩陣R ∈{0,1}n×N,V(s,t)是R(s,t)在(pk,sk)=(P,?t)下用GSW 加密算法[4]下加密的β噪音密文, 即V(s,t)=PTR+R[s,t]G, 其中(s ∈[n],t ∈[N]). 設(pk′,sk′)=(P′,?t′)為另一對密鑰. LinkAlgo算法輸入pk′和所有的V(s,t)∈Z(m+1)×Nq,輸出Y使得STY=STP′TR+e,‖e‖∞≤m3β（(e為噪音).

算法1 LinkAlgo 算法Input: pk′ 和{V (s,t)}s∈[n],t∈[N]Output: Y ∈Z(m+1)×N q(1) 定義Ls,t ∈Z(m+1)×N q, 其中s ∈[n],t ∈[N]{Ls,t[a,b] =P′[a,s];t = b 0;其他(2) 輸出Y =n∑N∑s=1t=1 V (s,t)G-1(Ls,t) ∈Z(m+1)×Nq

6 MMFHE 方案

-MMFHE.Eval(params, f,?C1,··· ,?Cl)→(?C*):

6.1 方案的安全性:

6.2 密文擴展的正確性:

7 結(jié)論

本文基于Dual.LWE 假設提出來一個支持多比特加密的多密鑰全同態(tài)加密方案, 該方案是選擇明文攻擊安全的. 相對于傳統(tǒng)的單比特單密鑰全同態(tài)加密方案, 該方案實現(xiàn)多比特多密鑰全同態(tài)加密, 但該方案的運行效率與實際應用還有一定的差距, 進一步提高全同態(tài)加密方案的效率和安全性仍然是全同態(tài)加密技術(shù)研究的重點與難點.