高效低存儲開銷可驗證外包求解大規模線性方程組方案

馮 達 周福才 王 強 吳淇毓

(東北大學軟件學院 沈陽 110169)

近些年云計算技術有了長足發展，目前已經有包括亞馬遜、谷歌、微軟、雅虎等許多著名公司提供了針對商業或個人的云計算服務.在云計算服務器上進行計算需要用戶外包數據到服務器，這樣會導致一系列安全問題[1-2].第1個安全問題是外包計算的隱私性：好奇的云計算服務器不應該了解關于外包計算的任何信息(包括輸入和輸出).第2個安全問題是外包計算的可驗證性：外包用戶應該能夠檢測出云計算服務器的任何惡意行為.另外，在效率方面，要求用戶設備需要完成的計算比求解本身計算更高效；在存儲開銷方面，要求外包方案盡量降低用戶所需存儲空間.

大規模線性方程組Ax=b是最基本的代數問題之一[3-4].許多現實問題會導致規模非常大且系數非常密集的線性方程組，甚至會有幾百萬個未知變量.這時，系數矩陣的存儲需求很容易超過用戶設備可用存儲空間.

由于外包服務器不可信，Golle和Mironov[5]最先提出了Ringers概念來解決驗證計算的信任問題. Gennaro等人[6]正式提出了可驗證計算的模型和方案.由于全同態加密技術效率過低，之后的一些方案[7-8]提高了可驗證計算的效率.Parno等人[9]提出一種多功能可驗證計算方案.

Atallah等人[10]提出了矩陣乘法和積分計算的安全外包框架.然而，該方案允許泄露私密信息.Atallah和Li[11]提出了一個安全外包序列比較到兩個服務器的高效協議.隨后Blanton等人[12]為安全外包序列比較提出了一個更有效的方案.Benjamin和Atallah[13]解決了外包線性代數計算的問題，但需要昂貴的同態加密操作.Atallah和Frikken[14]隨后提出基于Shamir秘密共享的改進方案.其他一些方案[15-16]也使用Shamir秘密共享在云上執行同態計算.顯然，基于秘密共享的協議需要至少2個非共謀服務器.Wang等人[17]提出了安全外包線性規劃計算的有效機制.隨后，Wang等人[18]又提出了一種基于迭代方法求解大規模線性方程組的安全外包機制，但需要客戶端和云計算服務器進行多輪交互.最近Yu等人[19]提出了基于矩陣變換的非迭代外包算法；Shen等人[20]提出了一種分布式安全外包方案；Zhang等人[21]提出了基于置換的外包算法；Chen等人[22]提出了基于稀疏矩陣的高效外包算法；蔡建興等人[23]提出了一個基于克羅內克函數和隨機置換的可驗證外包算法.

本文在完全惡意模型(fully malicious model)下提出了一個新的高效低存儲開銷可驗證外包求解大規模線性方程組方案EVLE-LS(efficient verifiable outsourcing of solving large-scale linear equations with low storage overhead).即本方案只需外包計算到單個云計算服務器，該服務器被認為是懶惰的、好奇的、不誠實的.本方案的優勢在于：與Gennaro等人在文獻[6]中提出的安全外包計算模型相比，取消了公鑰pk；在無需復雜的知識證明技術或者布爾亂碼電路的條件下實現了完全可驗證.在可驗證方面優于文獻[12]中的方案；在效率方面優于文獻[12，22]中的方案；客戶端與服務器只需一輪交互過程；與文獻[12，22-23]中的方案相比，利用構造的偽隨機稀疏矩陣生成算法大幅度降低所需存儲開銷到常數級.

1 相關知識

1.1 稀疏矩陣概念及性質

定義1.稀疏矩陣(sparse matrix).元素大部分為零的矩陣稱為稀疏矩陣.反之，如果大部分元素都為非零元，稱之為稠密矩陣.

設A,B是2個普通(非稀疏)n×n矩陣，計算AB或BA需要進行n3次標量乘法運算，即復雜度為O(n3).而若其中1個為稀疏矩陣，不失一般性，設A為每行最多有μ個非零元的n×n稀疏矩陣(μ?n)，B為任意n×n矩陣，計算AB或BA至多需進行μn2次標量乘法運算.由于μ?n，所以此時計算AB的復雜度為O(n2).

1.2 嚴格對角優勢矩陣理論

定義2.嚴格對角優勢矩陣(strictly diagonally dominant matrix).如果n階矩陣A的每一列主對角元素的絕對值均大于非主對角元素絕對值之和，即：

其中,j=1,2,…,n.

引理1.如果n階矩陣A=(ai j)為嚴格對角優勢矩陣，那么A是可逆的(非奇異的)[24].

1.3 可驗證性

因為需要對可驗證性進行討論，此處選用β-Checkability的概念衡量可驗證性.

定義3.β-Checkability[25].稱方案是功能F的β-Checkability的實現，如果：1)該方案正確實現了F功能；2)對任意輸入，服務器不遵守協議的行為都會被以不低于β的概率檢測出來.

1.4 矩陣的編碼和解碼[22]

客戶端外包形如Ax=b的大規模線性方程組，其中A是系數矩陣，b是系數向量.

1) 編碼過程

① 選取2個隨機的可逆稀疏矩陣M,N，令T=MAN，保證A的隱私性.

② 利用偽隨機數生成器(pseudo-random generator, PRG)生成一個隨機向量r，計算c=Ar+b,d=Mc.

T和d為編碼得到的結果.外包到云計算服務器得到返回結果y使得Ty=d.

2) 解碼過程

注意到:

d=Mc=M(Ar+b)=M(Ar+Ax)=
MA(x+r)=MAN·N-1(x+r)=Ty,

客戶端只需計算x=Ny-r即可求得方程組的解x.

2 EVLE-LS形式化定義及安全需求

EVLE-LS方案包括2方實體，分別是客戶端和服務器，如圖1所示:

Fig. 1 The architecture of EVLE-LS scheme圖1 EVLE-LS方案的體系架構

1) 客戶端對線性方程組問題進行編碼，將編碼后的問題發送給服務器;

2) 服務器進行計算尋找編碼后方程組的解，將編碼形式的結果返回給客戶端;

3) 客戶端對返回結果進行驗證并根據結果求出原線性方程組的解.

2.1 形式化定義

該外包線性方程組方案包含5個算法：密鑰生成算法、問題生成算法、計算算法、驗證算法和求解算法，即:

EVLE-LS=(KeyGen,ProbGen,
Compute,Verify,Solve).

每個算法的具體描述如下：

1) 密鑰生成算法KeyGen(λ)→(sk).給定一個安全參數λ作為輸入，客戶端執行該算法生成私鑰sk，并由客戶端保密.

2) 問題生成算法ProbGen(A,b,sk)→(σA,σb).客戶端執行該算法，以系數矩陣A、系數向量b和私鑰sk為輸入，返回值為A和b的編碼形式σA,σb.

3) 計算算法Compute(σA,σb)→σx.客戶端發送σA,σb到服務器，服務器以σA,σb為輸入計算σx滿足σAσx=σb，并返回σx到客戶端.

4) 驗證算法Verify(σx,sk)→1 or 0.客戶端以σx和sk為輸入執行該算法，驗證σAσx=σb是否成立.若通過驗證，則返回1(accept)，否則返回0(reject).

5) 求解算法Solve(σx,sk)→x.如果上一步執行Verify算法通過驗證，則輸入密鑰sk以及σx，客戶端運行該算法，輸出方程的解x.

2.2 安全需求

安全需求包括正確性，隱私性和不可偽造性.直觀上，正確性即結果是正確的；隱私性即服務器無法得知外包計算的任何相關信息；不可偽造性即服務器偽造的結果無法通過驗證.下面給出這3種需求的形式化定義.

2.2.1 正確性

首先給出定義輸出結果x正確性的實驗Experimentcorrectness：

(sk)←KeyGen(λ);
(A,b)←Challenger;
(σA,σb)←ProbGen(A,b,sk);
σx←Compute(σA,σb);
x←Solve(σx).

其中Challenger為挑戰者.假設該實驗中的算法均被正確執行.

定義4.如果Pr[Ax=b]≥1-negl(λ)，其中negl(λ)是關于安全參數λ的可忽略函數(下同)，則稱方案輸出結果x是正確的.

2.2.2 隱私性

1) 隱私性一方面指外包方程組的系數的隱私性.即該方案的交互過程中服務器無法得知關于方程組系數的任何信息.下面給出定義EVLE-LS方案中方程組系數隱私性的實驗Experimentpri-coef：

(sk)←KeyGen(λ);
((A0,b0),(A1,b1))←A;
(σA0,σb0)←ProbGen(A0,b0,sk);
(σA1,σb1)←ProbGen(A1,b1,sk);
b←{0,1};
b′←A(σAb,σbb).

定義5.如果對所有概率多項式時間(probabilistic polynomial time, PPT)敵手A，滿足:

則稱方程組的系數具有隱私性.

2) 隱私性另一方面指外包線性方程組的解的隱私性，即服務器無法得知關于方程組解的任何信息.給出定義EVLE-LS方案中解的隱私性的實驗Experimentpri-sol：

(sk)←KeyGen(λ);
(A,b)←Challenger;
(σA,σb)←ProbGen(A,b,sk);
σx←Compute(σA,σb);
x0←Solve(σx);
x1←Rn×1;
b←{0,1};
b′←A(σA,σb,σx,xb).

定義敵手A對于方程組解的隱私性的優勢為

定義6.如果對所有概率多項式時間敵手A，滿足:

則稱方程組的解具有隱私性.

2.2.3 不可偽造性

這里的不可偽造性指服務器無法惡意偽造一個結果返回給用戶并通過驗證.為了更加明確，給出定義不可偽造性的實驗Experimentunforgeability：

根據上述實驗，定義敵手對返回結果不可偽造性的優勢為

定義7.如果對所有概率多項式時間敵手A，滿足:

則稱服務器的返回結果具有不可偽造性.

3 EVLE-LS方案

本方案將存儲開銷降低到了常數級的核心在于構造了一個偽隨機稀疏矩陣的生成算法，客戶端只需保存常數個密鑰值.理論上可以用任意隨機的可逆稀疏矩陣來編碼LE問題中的輸入，保證輸入的隱私性.為了方便實現，選取稀疏的嚴格對角優勢矩陣(sparse strictly diagonally dominant matrix, SSDDM)作為編碼矩陣.在3.1節中給出稀疏嚴格對角優勢矩陣的生成算法，并在3.2節中給出了方案的詳細描述.

3.1 生成稀疏的嚴格對角優勢矩陣

為生成偽隨機的稀疏嚴格對角優勢矩陣，選取3個偽隨機數生成器Gpos,Gval,Gdiagval，具體描述為

Gdiagval:I×N→{0,1}B+B′,
(i,nonce)|→10…0‖Gval(i,i,nonce);

其中，Gpos用來生成稀疏嚴格對角優勢矩陣中非零元素的位置；Gval用來生成非零元的數值；Gdiagval用來生成矩陣對角元素的數值，確保對角元素隨機性和矩陣的嚴格對角優勢性質.下面給出SSDDM生成算法SSDDMGen的詳細描述.

SSDDMGen(k,nonce)→M：

① 初始化零矩陣Mn×n=(mi j)=0.

② 利用Gpos生成第i行非零元所在列的位置ki j.

④ 利用Gdiagval刷新矩陣主對角線上的數值，此處選擇簡單地將一個B′位的二進制數值串10…0(見注釋1)與Gval(i,i,nonce)連結起來，即令mi i=Gdiagval(i,nonce)作為主矩陣對角元素的值.

經上述SSDDMGen過程，由Gpos保證了每行非零元位置的隨機性，由Gval保證了非零元數值的隨機性(見注釋2)，由Gdiagval保證了主對角元素數值的隨機性并實現了矩陣的嚴格對角優勢性質.于是算法SSDDMGen實現了生成偽隨機稀疏嚴格對角優勢矩陣的功能.

注釋1.選擇高位補齊的數字時，需滿足補齊之后的數值10…0‖valuei i>(2B+1-1)n.上述算法中選擇了特定形式的B′位二進制數值串10…0，最差的情況是存在某一行全為{0,1}B中最大的非零元，所以為了滿足嚴格對角優勢性質，只需令B′>1+lbn.事實上，當Gpos按列生成行位置時，此處條件將變成B′>1+lbμ.

注釋2.如果Gval只有行和列2個輸入，就會導致每次生成的矩陣相同位置的值一定相同.為了防止這種情況發生，引入了新鮮值nonce.使用Gval生成valuei ki j時，要求nonce的取值永不重復.

3.2 方案的詳細描述

基于3.1節提出的關鍵算法，本節對EVLE-LS方案中的5個多項式時間算法即密鑰生成算法、問題生成算法、計算算法、驗證算法和求解算法給出詳細描述.

1) 密鑰生成算法

KeyGen(λ)→(sk)：客戶端運行該算法，給定一個安全參數λ作為輸入.算法選擇生成3個隨機密鑰k1,k2,k3∈{0,1}s(λ)，2個新鮮值nonce1,nonce2.然后令sk=(k1,k2,k3,nonce1,nonce2).為了確保之后生成的稀疏矩陣非零元的數值是不可預測的，此處nonce1,nonce2的取值永不重復，且nonce1≠nonce2.

2) 問題生成算法

ProbGen(A,b,sk)→(T,d)：客戶端運行該算法，輸入LE問題的系數矩陣A和系數向量b，以及算法KeyGen(λ)生成的密鑰sk.該算法利用sk對A和b進行編碼，詳細步驟如下：

① 利用3.1節中構造的SSDDMGen算法生成2個隨機的稀疏嚴格對角優勢矩陣.令

M=SSDDMGen(k1,nonce1),
N=SSDDMGen(k2,nonce2).

② 生成隨機向量r：

初始化向量r=(r1,r2,…,rn)T=0.選取適當的偽隨機數生成器

Gvector:{0,1}s(λ)→{0,1}Bn.

計算Gvector(k3)=t1‖t2‖…‖tn，其中ti∈{0,1}B.再對所有1≤i≤n，令ri=ti.

③ 對輸入進行編碼，使服務器無法得知關于系數矩陣A和系數向量b的任何信息：

客戶端計算：

T=MAN,
c=Ar+b,
d=Mc,

得到了T和d作為問題生成算法的輸出.

3) 計算算法

Compute(T,d)→y：客戶端將Τ和d發送給服務器，服務器以T和d為輸入，計算y的值使得Ty=d，并將結果y返回到客戶端.

4) 驗證算法

Verify(y)→1 or 0：客戶端利用sk恢復矩陣M,N驗證Τy=d是否成立.如果成立，Verify輸出1，表示該結果可信；反之Verify輸出0，表示結果不可信.

5) 求解算法

Solve(y,sk)→x：如果Verify輸出1，返回結果y可信，客戶端利用sk中的k3恢復向量r，并計算x=Ny-r.求得x即為外包方程組的解.

4 安全性分析

定理1.在完全惡意模型下，EVLE-LS方案得到的結果x是正確的.

證明. 假設方案中所有算法都得到正確執行，則有:

T=MAN,
c=Ar+b,
d=Mc,
x=Ny-r.

于是:

Ty=d?MANN-1(x+r)=Mc
?A(x+r)=Ar+b
?Ax=b.

所以,Pr[Ax=b]=1≥1-negl(λ).

證畢.

定理2.在完全惡意模型下，EVLE-LS方案中外包方程組的系數矩陣A、系數向量b和最終結果x具有隱私性.

又因為b=M-1d-Ar,x=Ny-r.因為r的隨機性可知系數向量b和方程組的解x是具有隱私性的.

綜上，

證畢.

定理3.在完全惡意模型下，EVLE-LS方案中服務器的返回結果是不可偽造的.

證畢.

注釋3.實際應用中會存在方程組無解的可能，下面考慮外包方程組無解的情況.由于Ax=b無解等價于Ty=d無解，此時服務器只需返回y=?.該結果正確性顯而易見.下面對此種情況的隱私性和不可偽造性進行說明.由定理2的證明過程，系數矩陣A、系數向量b的隱私性與y的存在性無關.唯一會泄露給服務器的信息是：外包的方程組無解，即x不存在.這一點在實際應用中并不會造成隱私泄露問題.又假設存在y*≠?可以通過驗證，則有Τy*=d，與方程Ty=d無解矛盾.

證畢.

綜上所述，當Ax=b無解時，本方案仍具有正確性、足夠的隱私性和不可偽造性.于是EVLE-LS方案可以在完全惡意模型中處理無解大規模線性方程組問題.

5 性能分析及方案對比

本節首先對EVLE-LS方案各階段算法的時間復雜度進行分析，再從效率、交互輪次、可驗證性、存儲開銷4個方面將該方案與之前已有方案進行對比，最后對效率進行測試.

5.1 時間復雜度分析

首先從方案中客戶端所需的時間復雜度方面對方案的性能進行討論.

客戶端的時間復雜度涉及3個階段：

1)ProbGen階段中各步驟的計算以及相應的操作次數為

M,N,r:7G,
T=MAN:2μn2M,
c=Ar+b:n2M+nA,
d=Mc:μnM,

其中,G表示偽隨機數生成運算，M代表乘法運算，A代表加法運算.由于G是時間上可忽略的簡單映射運算，映射和加法的操作時間與乘法相比是可以忽略不計的.于是可以得出此階段的時間復雜度為

((2μ+1)n2+μn)M～O(n2).

2)Verify階段中的計算及相應的操作次數為

M,N:6G,
MANy:((2μ+1)n2)M,

可知此階段的時間復雜度為

((2μ+1)n2)M～O(n2).

3)Solve階段中的計算及相應的操作次數為

r:1G,
x=Ny-r:μnM+nA,

可知此階段的時間復雜度為μnM～O(n).

5.2 方案對比

本節將EVLE-LS方案與文獻[12，22-23]中提出的方案進行對比.在效率方面，5.1節中已經給出了對EVLE-LS方案的分析.下面從交互輪次，可驗證性和存儲開銷3方面進行方案對比.

1) 交互輪次.文獻[12]中的方案是基于迭代理論的求解方法，但該方案要求客戶端和服務器進行L輪交互.而在文獻[22]中提出的方案是基于稀疏矩陣編碼的外包方案.該方案不需要迭代，也就不需要客戶端和服務器進行L輪交互，只需進行1輪交互.EVLE-LS方案也是利用稀疏矩陣對問題進行編碼，也具有客戶端與服務器只需進行1輪交互的優點.

3) 存儲開銷.與之前已有方案相比，EVLE-LS方案最大的優化在于存儲開銷方面.文獻[12，22-23]中提出的方案需要昂貴的存儲開銷O(n2)，即客戶端需要大量的存儲空間.在問題規模足夠大時，這種結果是不可接受的.而本方案利用構造的SSDDM生成算法，將存儲開銷降到了常數級.

下面將以上效率、交互輪次、可驗證性、存儲開銷4個方面討論結果匯總至表1所示：

Table 1 Capability Comparison with Prior Schemes表1 方案性能比較

Notes: M: An operation of multiplication; G: An operation of PRG; EN: An operation of Paillier encryption; DE: An operation of Paillier decryption;L: The round of iteration;l: A constant.

表1中M表示乘法操作，G表示偽隨機函數映射操作，EN和DE分別表示Paillier加密系統中的加密、解密操作.L是所需迭代次數，l是常數.

通過表1可以看出，本方案在效率、交互輪次、可驗證性和存儲開銷4方面均優于文獻[12]；在Solve階段的時間復雜度優于文獻[23]；與文獻 [12，22-23]相比，以可忽略的操作時間為代價，增加了稀疏嚴格對角優勢矩陣的生成算法.并利用該算法大幅度降低存儲開銷到常數級.

5.3 效率測試

通過5.2中的理論分析，已經說明了方案的優越性，下面對本方案中服務器端的各階段算法效率進行測試.實驗中，測試工具為MATLAB R2017b，客戶端配置為Intel?CoreTMi5-7400 3.0 GHz主頻的處理器和8 GB內存.選定L=100，對問題生成算法、驗證算法、求解算法3個階段進行測試.

Fig. 2 Comparison for time consumptions of ProbGen圖2 問題生成算法執行時間對比

首先比較4個方案中問題生成算法階段的效率，實驗結果如圖2所示，橫坐標為矩陣規模的大小，縱坐標為該算法運行的時間.可以看出在該階段，本方案效率與文獻[22-23]中方法基本持平，均為二次曲線，但優于需要Paillier加密操作的文獻[12]所述方法.

對比驗證算法階段的效率，實驗結果如圖3所示.可以看出本方案與文獻[22-23]在該階段效率均為二次曲線，但不受迭代次數L值影響，優于文獻[12].

Fig. 3 Comparison for time consumptions of Verify圖3 驗證算法執行時間對比

對比求解算法階段的效率，實驗結果如圖4所示.從圖4中容易看出，在求解算法階段，本方案的時間消耗與問題規模n呈線性關系，算法效率與文獻[22]相近，均與問題規模呈線性關系，明顯優于文獻[23].文獻[12]也屬線性關系，但涉及Paillier解密操作導致斜率較大.

Fig. 4 Comparison for time consumputions of Solve圖4 求解算法執行時間對比

最后比較4個方案中客戶端保存密鑰的存儲開銷，實驗結果如圖5所示，圖5中橫坐標為問題規模大小，縱坐標為所需存儲空間大小.顯然，文獻[12，22-23]都需要昂貴的存儲開銷，只有本方案將存儲開銷降到了常數級.

Fig. 5 Comparison for storage overhead圖5 存儲開銷對比

以上結果表明:EVLE-LS方案優于之前的文獻[12，22-23]中方法.

6 總 結

本文研究了安全外包大規模線性方程組問題.針對現有方案存在效率過低或存儲開銷過大等問題，構造了一種偽隨機的稀疏嚴格對角優勢矩陣生成算法，并基于該算法提出了一種新的外包大規模線性方程組方案.該方案取消了公鑰，并大大降低了需要在客戶端存儲的私鑰規模，具有高效率、低存儲開銷、完全可驗證、無需與服務器進行多輪交互的優點.總體來說，該方案優于其他已有方案，對于存儲能力有限的客戶端安全外包大規模線性方程組問題具有一定理論指導和實際應用價值.