基于多密鑰全同態(tài)加密方案的無CRS 模型安全多方計算*

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

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

1 引言

2 準備工作

2.1 記號

對于自然數(shù)n, [n] 代表{1,2,··· ,n}. 小寫黑體字母a 代表向量, 大寫黑體字母A 代表矩陣. a[i] 表示向量a 中第i 個元素, a 的無窮范數(shù)用//a//∞表示, //a//∞=maxi(|a[i]|). 矩陣的無窮范數(shù)定義與之類似. (a,b) 代表兩個向量的內(nèi)積, (a|b) 表示兩個向量的水平連接. 一個n×m 維全為0 的矩陣用0n×m表示. X 代表一個有限域? 中的分布, ω ←X 表示ω 從分布X 隨機選取.

2.2 定義與定理

3 GSW 全同態(tài)加密方案

本節(jié)我們回顧GSW 全同態(tài)加密方案的構(gòu)造、同態(tài)操作以及噪音分析. GSW 是由一系列概率時間多項式算法組成, 即GSW = (SetUp,KeyGen,Enc,Dec,Eval), 其中Eval 算法包含AddEval, MultEval,ANADEval.

4 無CRS 的多密鑰全同態(tài)加密方案

4.1 單密鑰密文到多密鑰密文

易見//ej//∞≤Bχ. 其中tj為參與方Pj的私鑰.

引理2 (擴展安全性) 在LWE 假設(shè)成立的情況下, 上述擴展過程是選擇明文安全的.

下面我們用兩個參與方來簡要說明上述擴展過程.

4.2 方案的構(gòu)造

4.2.1 擴展的正確性

4.3 與KLP 方案的對比

從效率上看, KLP 方案的擴展過程需要對隨機矩陣R ∈{0,1}m×m中每一個元素用GSW 全同態(tài)加密的加密過程進行加密, 然后生成nmN 個n×m 維矩陣用來計算輔助信息X. 而本文中的方案只需要對R 進行一次編碼, 之后通過Link 算法即可得到輔助信息X.

從內(nèi)存上看, KLP 方案每一個參與方在生成擴展密文時需要需要計算存儲m2+nmN 個n×m 維矩陣. 而本文中的方案只需計算存儲一個m×ml 維矩陣以及N 個n×m 維矩陣即可.

從噪音上看,KLP 方案最終的解密噪音為2(m4+m)mNBχ.而本文中的解密噪音(2+m)mNBχ,遠遠小于KLP 方案中的解密噪音.

5 基于門限MFHE 的三輪安全多方計算協(xié)議

利用上述的門限多密鑰全同態(tài)加密方案構(gòu)造一個三輪安全多方計算協(xié)議, 該協(xié)議既不需要CRS 也不需要復(fù)雜的參數(shù)設(shè)置. 而且三輪的輪數(shù)在無CRS 模型中是最低的, 因為協(xié)議中沒有CRS, 每一個參與方完全獨立的生成自己的密鑰對, 并在協(xié)議開始前分發(fā)出去, 這至少需要一輪, 接下來如文獻[9] 類似, 構(gòu)造一個兩輪的協(xié)議用來生成與發(fā)布密文以及計算發(fā)布部分解密, 故至少需要三輪來完成整個協(xié)議. 該協(xié)議在面對一個半惡意的敵手是安全的, 這一類型的敵手要比惡意敵手弱但比半誠實的敵手強. 我們根據(jù)文獻[7]給出半惡意敵手的定義.

定義8 (半惡意敵手) 一個半惡意的敵手可以腐敗任意多個誠實方, 除了標準磁帶外, 還擁有一個證據(jù)磁帶, 該敵手必須將自己代表的誠實方的輸入記錄到證據(jù)磁帶上. 敵手可以根據(jù)輸入和一定的隨機性來決定是否忠實的履行協(xié)議.

對于一個半惡意的模型, 可以通過理想現(xiàn)實模型來證明其安全性. 即通過一系列游戲來證明理想現(xiàn)實.

5.1 協(xié)議的構(gòu)造

f({0,1})N→{0,1} 是一個可計算函數(shù), d 代表函數(shù)f 的電路深度. 假設(shè)共有N 個參與方, 用{Pi}i∈[N]表示.

輸出: 每個參與方 Pi收到其他參與方的部分解密 {pj}j?=i, 運行最終解密算法得到: y ←MFHE.FinDec(p1, ··· , pN). 輸出y =f(x1,··· ,xN).

5.2 協(xié)議的安全性

6 結(jié)論

本文基于LWE 假設(shè)提出了一個無CRS 模型的多密鑰全同態(tài)加密方案, 并以此方案為基礎(chǔ), 構(gòu)造了無CRS 模型的三輪安全多方計算協(xié)議, 并且在面對一個半惡意的敵手是安全的. 如第4 節(jié)所描述該協(xié)議的輪數(shù)在無CRS 模型中是最優(yōu)的, 文中4.3 節(jié)將該方案與原有方案做對比, 無論是效率還是內(nèi)存開銷, 本文中的方案都優(yōu)于原有方案, 而且解密噪音也遠遠低于原有方案.

該協(xié)議接下來需要研究的是如何在一個無CRS 模型中構(gòu)造一個可以抵抗惡意敵手的安全多方計算協(xié)議; 如何在協(xié)議執(zhí)行過程中, 提高數(shù)據(jù)在傳輸過程中的安全性以及會話的協(xié)同性.