基于格密碼的矩陣乘可驗證計算方案

陳澤

(四川大學網絡空間安全學院，成都610207)

0 引言

云計算可以協調大量計算機資源，從而提供給客戶強大的存儲和計算能力，大大提高計算資源的利用率。然而云計算也帶來了新的安全問題：云平臺可能錯誤執(zhí)行客戶的應用程序或者安全性無法保證，甚至其自身存在惡意行為，這些都可能侵害到客戶數據的隱私性以及完整性以及計算結果的正確性。傳統的方法，例如審計依賴于發(fā)生錯誤的頻率，而冗余計算無法解決服務器之間相互串通的情況[1]。相比之下，可驗證計算協議能夠為用戶提供一種無需重新本地運行在服務端所部署的程序也可驗證結果正確與否的途徑，且錯誤結果通過驗證的概率是幾乎可以忽略的。然而，雖然可計算協議在近些年來已經有了很大的進展，但適用于任何場景的可驗證計算協議的性能開銷仍與可應用階段存在很大的距離。另外，隨著同態(tài)加密技術的發(fā)展，基于同態(tài)加密算法構建一個可實現的適用于特定場景的可驗證計算協議已成為可能。

矩陣乘在科學以及工程領域中十分普遍。對兩個l×l的矩陣而言，傳統的算法計算其乘積的復雜度為O(l3)。隨著數據量的增大，l可能會達到幾萬甚至更高，而此時計算其乘積的空間以及時間開銷都是個人計算能力難以承受的。本文在現有的基于格理論的同態(tài)加密算法基礎上，構建了一個具有隱私保護的用于矩陣乘的可驗證計算協議。由于格理論上的問題在量子計算機下仍是難解的，本文的協議具有抗量子分析的安全性以及隱私性，且本地的計算開銷遠小于直接計算矩陣乘所造成的開銷。

1 設計原則和研究現狀

(1)正確性。在服務器誠實且正確地執(zhí)行Compute算法的情況下，Verify算法接受服務器返回的結果，且在解碼后正是客戶端所外包的計算任務的正確結果；

(2)安全性。即可驗證性。由于硬件的故障或者軟件的漏洞等意外原因，或服務器本身是敵對的或者自私的，其返回計算結果可能是錯誤的。安全性要求一個錯誤的結果能夠成功欺騙Verify算法的可能性是可忽略的。

(3)高效性?？沈炞C計算協議所產生的本地的計算開銷應低于所外包的任務的開銷。對矩陣乘的應用場景而言，協議所需的本地計算量應低于O(m3)。

除此之外，隱私對于個體以及商業(yè)公司來說，也是十分重要的問題。用戶在外包過程中的原數據可能是敏感或者機密的，一些好奇的或帶有惡意的云端可能會將這些數據存儲起來以備后用。除以上性質外，一個具有隱私保護的可驗證外包協議還應具有隱私性，即敵手在多項式時間內分辨出由已知明文和隨機串產生的密文的概率是微乎其微的。接下來我們介紹國內外現有的針對矩陣乘的可驗證計算協議。

Atallah等人于2010年提出了一種可以用于矩陣乘法的可驗證計算協議[3]。該方案主要基于Shamir密鑰分享協議。用t表示Shamir密鑰分享協議中多項式的次數，對于每個要計算乘積的矩陣對，該協議需要生成16t+4個矩陣對。除此之外，對服務器返回的結果，客戶端需要利用插值法依次還原出每個元素，因此該方案的計算復雜度為O(t2m2)。

Mohassel于2011年提出了一種針對矩陣乘法的可驗證計算協議[4]。文中使用同態(tài)算法(GHV或者BGN)對明文矩陣A和B加密，并將密文發(fā)送至服務器；在服務器返回計算結果后，客戶利用私鑰對其解密獲得矩陣C。之后客戶生成m維隨機向量v，并驗證ABv=Uv是否成立。如果成立，則接受該計算結果?？傮w來看，該方案中客戶的計算開銷主要來自于其基于的加密算法對矩陣的加密和解密運算。然而其基于的GHV算法的復雜度為O(m3)，與矩陣乘法復雜度相當。后來在文獻[5-6]中提出的協議中也應用了此類驗證方式，然而文獻[5]中僅對原矩陣進行了隨機的行列變換，文獻[6]中利用隨機的掩碼矩陣與原矩陣相加來保護用戶的數據，這樣的方式并沒有嚴格的安全性證明，其隱私性以及安全性都是沒有保證的。

除此之外，在文獻[7-8]中提出的基于雙線性對的驗證算法實現了公開驗證的性質，即客戶可以將驗證的工作交給公開的第三方，第三方在無需獲知用戶私鑰和原數據的情況下可以驗證結果的正確性。該性質雖然有一定的實用意義，但也為客戶帶來了很大的額外開銷，包括生成滿足雙線性性質的群，以及對每個元素分別預處理所帶來的O(m2)次冪運算。

由表16知，回歸方程為：Y=261.509+6.495X1+2.133X2+0.426X3-0.605X4.

2 協議描述

本文中矩陣和向量分別用加粗的大寫字母和小寫字母表示(例如矩陣A，向量a)。用n表示安全參數，q=poly(n)為模數，Z表示整數集，Zq表示有限域Z/qZ。定義M次分圓多項式ΦM=xd+1，其中M為2的冪次，d=φ(M)=M/2。定義R=Z[x]/ΦM，Rq=Zq[x]/ΦM。定義以下分布：χk表示多項式的系數向量在{-1，0，1}d均勻分布；χσ表示多項式的每個系數選自標準差為σ的離散高斯分布。

為了構造用于矩陣乘的可驗證計算協議，我們首先引入Halevi等人于2018年提出的同態(tài)加密算法HPS18[9]。該算法是在Fan、Vercauteren所提出的同態(tài)加密算法[10]基礎上的RNS變種，其算法結構和運行效率較原算法都有了較大的優(yōu)化提升。該算法的安全性基于環(huán)上的誤差學習問題(Ring Learning with Errors，RLWE)：用χ表示R上的某個分布，對于e←χ，s∈Rq，在多項式環(huán)Rq均勻選取(a，b)，RLWE問題指分辨(a，b)和(a，(a，s)+e)兩個分布是困難的。HPS18加密算法的具體步驟如下：

c) Decsk(c)：對于密文c=(c0，c1)，計算h=[c0+c1s]q，還原明文m=[(x·p/q)]p。

d) EvalAddevk(c1，c2)：對于輸入的兩個密文c1和c2，其同態(tài)加的結果為[c1+c2]q；

本文用于矩陣乘的可驗證計算協議構建在上述算法之上。在下面描述中，使用矩陣X，Y∈Rl×l表示明文的數據；外包給服務器的函數為計算H=XY。我們的協議具體步驟如下：

a) KeyGen(1n)：安全參數為n，用戶端調用KeyG(1n)生成公私鑰對(sk，pk)以及計算密鑰evk。

d) Verify(S，SK)：客戶端首先對S中的每個元素進行解密：hi，j=Decsk(si，j)。對每個i∈[1，u]，計算Hvi=wi是否成立。若全部成立，則接受此次的計算結果，反之拒絕。

3 協議分析

上述協議的正確性和隱私性是顯然的，而其可驗證性基于如下引理：

引理1[4]：給定兩個不同的矩陣A，A′∈Rl×l(其中R為有限交換環(huán))，隨機選取v∈Rl，我們有Pr(Av=A′v)≤1/|R|。

由此可見，服務器以一個錯誤結果成功欺騙客戶的概率為|R|-p。又因為u=poly(n)，該概率對安全參數n而言是可忽略的，可驗證性成立。最后，本協議的各項性質以及與現有的一些相關協議的比較如表1所示。

表1 文中協議與其他現有同類協議對比

表1中梳理了文中提到的協議的各項性質。為了簡潔起見，表1中的計算開銷僅包括了模內加法運算(ta)、乘法運算(tm)以及指數運算(te)所需的時間開銷。由此可見，本文中的協議無需使用相較昂貴的指數運算，其效率較大部分同類協議高；由于其基于的困難性問題為RLWE問題，也達到了較高的安全性。

4 結語

本文梳理總結了近年來用于矩陣乘的可驗證計算協議，并在現有的同態(tài)算法以及驗證框架基礎上構造了一種高效的并帶有隱私保護的用于矩陣乘的可驗證計算協議。相比于現有的方案，本方案具有抵抗量子分析的隱私性以及較高的效率。下一步，將針對進一步提高加密以及驗證效率和更復雜的應用場景展開研究。