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

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

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

1 引言

2 準(zhǔn)備工作

2.1 記號(hào)

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

2.2 定義與定理

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

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

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

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

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

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

下面我們用兩個(gè)參與方來簡(jiǎn)要說明上述擴(kuò)展過程.

4.2 方案的構(gòu)造

4.2.1 擴(kuò)展的正確性

4.3 與KLP 方案的對(duì)比

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

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

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

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

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

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

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

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

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

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

5.2 協(xié)議的安全性

6 結(jié)論

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

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