劉振華, 李賓, 白翠翠

(1.西安電子科技大學 數(shù)學與統(tǒng)計學院，陜西 西安710071；2.桂林電子科技大學，廣西信息科學實驗中心，廣西 桂林541004)

?

可驗證的凸二次規(guī)劃安全外包協(xié)議

劉振華1,2, 李賓1, 白翠翠1

(1.西安電子科技大學 數(shù)學與統(tǒng)計學院，陜西 西安710071；2.桂林電子科技大學，廣西信息科學實驗中心，廣西 桂林541004)

為了降低資源受限用戶求解凸二次規(guī)劃問題的計算量，提出了可驗證安全的凸二次規(guī)劃外包計算協(xié)議。 新協(xié)議首次引入置換技術，將原始問題盲化轉(zhuǎn)換成隨機問題，然后外包給云服務器求解，最后驗證服務器返回結(jié)果，減少了用戶端的計算量。 安全性分析表明，在完全惡意模型下，新協(xié)議可以保證輸入輸出數(shù)據(jù)的隱私性，且能以最優(yōu)的概率檢測出云服務器的不誠實行為。仿真實驗表明，與現(xiàn)有協(xié)議相比，新協(xié)議中用戶在轉(zhuǎn)換和驗證階段所需時間明顯降低。

云計算；凸規(guī)劃；二次規(guī)劃；外包計算；隱私保護

云計算[1]是一種新興的基于互聯(lián)網(wǎng)的計算模式。作為并行計算、網(wǎng)格計算、分布式計算的發(fā)展，云計算具有高可靠性、可擴展性、經(jīng)濟性、服務多樣性等顯著特點。云計算可以為企業(yè)與個人提供方便快捷的網(wǎng)絡訪問、存儲、軟件、外包等多種服務，具有廣闊的發(fā)展前景，近些年來也受到了各行各業(yè)的廣泛關注。

外包計算[2]作為云計算的服務方式之一，是將云服務器強大的計算能力作為一種公共設施為用戶提供計算服務。資源受限的用戶可以將計算代價高的計算任務外包給云服務器，從而節(jié)省用戶本地的資源開銷。盡管外包計算具有眾多好處，但也面臨著一些不可避免的安全威脅和挑戰(zhàn)。一方面，用戶外包出去的數(shù)據(jù)通常包含自己的隱私信息[3]，比如銀行賬戶信息、身份信息等。為了防止隱私信息的泄漏，用戶必須在將計算任務發(fā)送給云服務器之前對隱私數(shù)據(jù)進行加密，但普通的加密算法會破壞數(shù)據(jù)原有的計算特性，導致云服務器無法對密文執(zhí)行任何有效的計算，從而使得外包計算沒有意義。另一方面，由于外包計算過程中云服務器內(nèi)部操作的不透明性[4]，會導致云服務器可能會因某種動機而做出不誠實的行為，例如：在用戶無法驗證計算結(jié)果的情況下，對需要大量計算與存儲資源的計算任務，云服務器可能會受到經(jīng)濟利益的驅(qū)動而不執(zhí)行全部計算并返回一個計算上不可區(qū)分(錯誤)的結(jié)果，從而節(jié)省自己的計算代價；或者云服務器會在計算過程中試圖記錄與用戶隱私相關的信息，比如用戶的輸入/輸出數(shù)據(jù)。此外，云服務器中可能存在的軟件漏洞或者外部惡意攻擊都會使得計算結(jié)果的有效性受到影響。這些挑戰(zhàn)與威脅使得用戶數(shù)據(jù)的隱私性、計算結(jié)果的可驗證性問題已成為制約外包計算快速發(fā)展的重要因素。因此，研究如何實現(xiàn)外包計算中計算結(jié)果的可驗證性，保護用戶數(shù)據(jù)的隱私性具有實際意義。

凸二次規(guī)劃是一類常見的數(shù)學規(guī)劃問題，廣泛應用于經(jīng)濟管理、工程設計、分子研究和模式識別等科學工程領域。然而，這些實際問題通常需要求解大規(guī)模的凸二次規(guī)劃問題。例如工程設計中一個典型的雙精度50 000×50 000階矩陣需要大約20GBytes的存儲空間[5]，而普通用戶的設備(比如筆記本，PC等)無法滿足這樣的計算要求。因此，計算能力或資源受限的用戶可以選擇將大規(guī)模優(yōu)化求解問題外包給具有強大計算與存儲能力的云服務器。張鴻博等[6]基于矩陣轉(zhuǎn)換技術提出了凸二次規(guī)劃外包協(xié)議(記為Zhang-Shuang協(xié)議)，但協(xié)議中用戶端的計算復雜度為O(nρ)(2<ρ≤3)。

為了進一步減少外包計算過程中用戶端的計算量，通過引入置換技術，本文提出了新的可驗證的凸二次規(guī)劃安全外包協(xié)議。安全性和效率分析表明，新協(xié)議不僅可以保護用戶數(shù)據(jù)的隱私性、實現(xiàn)計算結(jié)果的可驗證性[7]，而且用戶端在轉(zhuǎn)換階段和驗證階段的計算量均低于已有協(xié)議。

1　背景知識

1.1凸二次規(guī)劃

凸二次規(guī)劃是一個應用廣泛的優(yōu)化問題，通常情況下，它可以用下面的標準形式描述：

(1)

式中：A、B為系數(shù)矩陣，Q是n階正定矩陣，b、c、d是n維列向量。本文中假設系數(shù)矩陣A和B為n階非奇異稠密矩陣。

考慮凸二次規(guī)劃解的三種情形[8]：

1)有可行解——該問題有一個最優(yōu)解能夠滿足所有的約束條件；

2) 無可行解——該問題沒有一個解可以使得所有的約束同時得到滿足；

3)無界——當約束條件都滿足時，目標函數(shù)值為任意小(或任意大)。

1.2凸二次規(guī)劃對偶理論

若原始凸二次規(guī)劃問題與其對偶問題中有一個問題具有最優(yōu)解，則兩個問題都存在最優(yōu)解。而且，原始問題與其對偶問題的最優(yōu)值相等。

定理1 若原始凸二次規(guī)劃問題與其對偶問題中有一個問題的目標函數(shù)值無界，則另一個問題無可行解。

1.3置換函數(shù)、克羅內(nèi)克函數(shù)

置換函數(shù)廣泛應用于群理論以及組合數(shù)學之中，可以表示為如下形式：

令π表示上述置換函數(shù)，π-1表示置換函數(shù)π的逆?？肆_內(nèi)克函數(shù)，又稱為克羅內(nèi)克δ函數(shù)，是一個二元函數(shù)，可以表示為如下形式：

1.4外包計算形式化定義

Gennaro等[10]在CRYPTO 2010提出了一個可驗證的外包方案，并給出了安全外包計算的形式化定義。形式化定義如下：

假設用戶將一個計算代價高的計算任務F(x)外包給不可信的云服務器，其中x∈D。一個安全的外包算法包括4個子算法，分別為密鑰生成(KeyGen)，問題轉(zhuǎn)換(ProTrans)，解決問題(Compute)，驗證(Verify)。

1)KeyGen(F,λ)→(PK,SK):此算法為隨機化的密鑰生成算法。輸入安全參數(shù)λ，生成一個密鑰PK將目標函數(shù)F加密，同時生成一個私鑰SK，由用戶自己保存。

2)ProTransSK(x)→(σx,τx):問題轉(zhuǎn)換算法運用私鑰SK將原始問題的輸入x∈D加密為一個公共值σx并將其發(fā)送給云服務器，用戶自己保存秘密值τx。

3)ComputePK(σx)→σy:云服務器運用密鑰PK以及經(jīng)加密后的輸入σx進行計算，并計算出一個盲化的結(jié)果σy，其中，y=F(x)。

4)VerifySK(τx,σy)→y∪⊥:用戶運用自己的私鑰SK和秘密值τx進行驗證。若驗證算法通過，則用戶通過將σy解密得到問題的解y，否則驗證算法輸出“⊥”，即盲化的結(jié)果σy為無效值。

1.5外包計算模型

本文考慮的外包計算模型包含兩個實體：用戶和云服務器，如圖1所示。用戶生成私鑰，對原始問題進行轉(zhuǎn)換并將轉(zhuǎn)換后的新問題發(fā)送給云服務器，云服務器解決新問題后將其解與解的正確性證明返回給用戶，用戶運用自己的私鑰進行解密和驗證，若驗證通過，則用戶得到原始問題的解，否則，用戶選擇報錯。

外包計算協(xié)議中，根據(jù)云服務器可信程度的不同，服務器模型可以分為誠實模型、半誠實模型和完全惡意模型[2]。誠實模型中，云服務器會誠實地執(zhí)行外包計算協(xié)議，并把正確的計算結(jié)果返回給用戶。在半誠實模型中，云服務器一方面會誠實地執(zhí)行外包計算協(xié)議，把正確的計算結(jié)果返回給用戶，另一方面會試圖利用執(zhí)行協(xié)議過程中得到的所有信息來獲取與用戶相關的隱私信息。本文中，假設云服務器為＂完全惡意＂的，即云服務器會表現(xiàn)為有意的破壞、停止協(xié)議的執(zhí)行，給用戶返回一個計算上不可區(qū)分的(無效)計算結(jié)果，同時其希望不會被用戶發(fā)現(xiàn)。

圖1　外包計算模型Fig.1　Outsourcing computation model

一個可驗證的安全外包計算協(xié)議必須滿足以下幾個性質(zhì)[11]：

1) 正確性：任何誠實的按照外包計算協(xié)議執(zhí)行的云服務器所返回的計算結(jié)果必然能被用戶接受。

2) 合理性：沒有一個云服務器返回的錯誤結(jié)果可以以不可忽略的概率被用戶接受。

3) 隱私性：在云服務器與用戶執(zhí)行協(xié)議過程中，云服務器不能推導出來與用戶隱私數(shù)據(jù)相關的敏感信息。

4) 高效性：外包協(xié)議中用戶端本地的計算量要遠小于其獨立解決該問題的計算量。

5) 可驗證性：外包協(xié)議中用戶可以以不可忽略的概率驗證云服務器返回的計算結(jié)果的正確性和不正確性。

2　協(xié)議描述

密鑰生成：用戶選擇兩個維隨機盲化系數(shù)向量，三個非零隨機數(shù)集合：

M(i,j)=αiδπ1(i),j，N(i,j)=βiδπ2(i),j，J(i,j)=γiδπ3(i),j，M、N、J均為可逆矩陣，其中M-1(i,j)=(αj)-1δπ1-1(i),j，N_1(i,j)=(βj)-1δπ2-1(i),j，J-1(i,j)=(γj)-1δπ3-1(i),j。根據(jù)生成的矩陣及隨機向量，定義私鑰SK=(M,N,J,r0,r1)。

2.1問題轉(zhuǎn)換

運用私鑰，用戶將原始問題(1)轉(zhuǎn)換為兩個新的問題。為了保護輸入與輸出數(shù)據(jù)的隱私性，采用以下轉(zhuǎn)換算法對敏感信息進行隱藏：

1)隱藏等式約束

為了保護向量中包含的隱私信息，用戶運用私鑰中可逆矩陣N及維向量ri(i=0,1)，在本文中采用仿射變換將向量x映射為向量y=N-1(x+ri)，則x=Ny-ri。將x=Ny-ri代入等式Bx=d得到等式：BNy=Bri+d。為了保護輸入數(shù)據(jù)B的隱私性，在等式左右兩邊同時乘以可逆矩陣M，即：

BNy=Bri+d→MBNy=M(Bri+d)→B′y=di

其中,B′=MBN，di=M(Bri+d)。

2)隱藏不等式約束

由于對于滿秩矩陣J，Ax≤b成立時不等式JAx≤Jb不一定成立，所以不能用上述方式隱藏不等式約束中的隱私數(shù)據(jù)[5]?？紤]到滿足不等式Ax≤b的向量x，均要滿足等式約束Bx=d，因此利用等式約束來隱藏不等式約束中的隱私數(shù)據(jù)。具體方法如下：

3)隱藏目標函數(shù)

通過以上三個部分對原始問題中敏感信息的隱藏，將原始問題(1)轉(zhuǎn)換為新的凸二次規(guī)劃問題CQP′，形式如下：

(2)

記F0=(Q′,A′,B′,b0,c0,d0)，F(xiàn)1=(Q′,A′,B′,b1,c1,d1)，且F0與F1為轉(zhuǎn)換后的兩個凸二次規(guī)劃問題。

2.2云端解決問題

云服務器接收到新問題F0與F1，分三種情況進行求解：

1)有可行解：服務器運用現(xiàn)有的CQP算法求解F0與F1并將結(jié)果y0和y1返回給用戶。

2)無可行解：云服務器返回F0與F1所對應的輔助問題的最優(yōu)值w0與w1，和對應的輔助問題的解y0和y1。

3)無界：云服務器返回與所對應的對偶問題的輔助問題的最優(yōu)值與，和對應的對偶問題的輔助問題的解y0和y1。

2.3用戶驗證

根據(jù)解的情況，驗證算法同樣分為3種情況：

Case1 有可行解：云服務器返回F0與F1的解y0和y1。用戶計算x0=Ny0-r0，x1=Ny1-r1。若x0=x1，則輸出原始問題的解x=Ny0-r0=Ny1-r1。否則，用戶輸出＂error＂終止協(xié)議。

Case2無可行解：云服務器返回問題無可行解。為了驗證云服務器是否誠實地執(zhí)行了計算，用戶通過構(gòu)造問題CQP′的輔助問題進行驗證其是否有可行解。其輔助問題可以表示為：

(3)

根據(jù)對偶理論，問題CQP′有可行解當且僅當輔助問題(3)有最優(yōu)解w=0。因此，用戶首先驗證是否有：w0>0和w1>0成立，若不成立，則輸出＂error＂終止協(xié)議；否則，用戶按照有可行解時驗證y0和y1的正確性，如果成立則說明該問題無可行解，否則選擇輸出＂error＂終止協(xié)議。

Case3無界：云服務器返回問題無界。由對偶理論知，若原始問題的目標值為無界，則其對偶問題無可行解。用戶可以通過驗證其對偶問題的可行性來判斷該問題是否有界。問題CQP′(2)的對偶問題如下：

其中，α與β為n維向量。類似于無可行解的情況，用戶驗證對偶問題的輔助問題的最優(yōu)值的正確性，然后驗證其對應解的正確性，最后得出結(jié)論。

3　協(xié)議分析

3.1安全性分析

參考外包計算領域前人的工作，給出了本文協(xié)議的安全性分析。

定理2：在完全惡意模型。中，該協(xié)議是可驗證的凸二次規(guī)劃安全外包協(xié)議。

證明：正確性：該協(xié)議的正確性是顯然的。若云服務器誠實地按照協(xié)議執(zhí)行，用戶就一定會接受它的輸出。

此外，證明轉(zhuǎn)換后的凸二次規(guī)劃問題與原始問題是等效的，即轉(zhuǎn)換后問題CQP′的最優(yōu)解y所對應的x是原始問題CQP的最優(yōu)解。證明如下：

假設y是CQP′的最優(yōu)解，x=Ny-r不是原始問題的最優(yōu)解，則一定存在x*滿足

且滿足約束Ax*≤b，Bx*=d，進一步得到x*=Ny*-r，滿足以下不等式：

即存在比y更優(yōu)的解y*滿足

與假設y為問題CQP′的最優(yōu)解矛盾。因此當y是轉(zhuǎn)換后的凸二次規(guī)劃問題CQP′的最優(yōu)解時，y所對應的x是原始問題的最優(yōu)解。

隱私性：首先證明輸入數(shù)據(jù)b,c,d和輸出數(shù)據(jù)x的隱私性。整個計算協(xié)議中，敵手可以獲得的全部信息為記

F0=(Q′,A′,B′,b0,c0,d0)，F(xiàn)1=(Q′,A′,B′,b1,c1,d1)，

另外，有以下等式成立：

向量r0與r1的隨機性保證了輸入數(shù)據(jù)b,c,d與輸出數(shù)據(jù)x的隱私性。

其次，首先證明輸入數(shù)據(jù)B的隱私性，同理可證新協(xié)議保護了輸入數(shù)據(jù)Q,A的隱私性。輸入數(shù)據(jù)B的隱私性由以下兩個階段實現(xiàn)：

可驗證性：用戶得到云服務器的計算結(jié)果y0與y1后，驗證等式Ny0-r0=Ny1-r1是否成立。由于云服務器偽造y0與y1，且使得該等式成立的概率是可以忽略不計的，因此一旦云服務器在協(xié)議執(zhí)行中有不誠實行為，用戶都可以在計算復雜度為O(n)的代價下以100%(最優(yōu))的概率檢測出來。

表1　計算量比較

3.2性能比較

表1給出了Zhang-Shuang協(xié)議以及本文協(xié)議在解密階段、轉(zhuǎn)換階段以及驗證階段效率的比較分析，其中n表示矩陣Q、A、B、M、N、J的階數(shù)，ρ滿足2<ρ≤3。求解標準形式凸二次規(guī)劃問題的計算復雜度為O(n3)[14]。本文協(xié)議中，用戶端在轉(zhuǎn)換和驗證階段的計算復雜度分別為O(n2)、O(n)，且均比Zhang-Shuang協(xié)議[6]有所減少，因此本文協(xié)議在效率方面更為高效。

3.3仿真實驗

為了驗證本文協(xié)議的高效性，對本文協(xié)議與Zhang-Shuang協(xié)議在轉(zhuǎn)換階段與驗證階段的效率進行了實驗評估比較。實驗環(huán)境采用Intel(R)Xeon(R)3.3-GHz CPU、8GB RAM臺式機、Windows7操作系統(tǒng)和Matlab程序語言。實驗中選取了中小規(guī)模的凸二次規(guī)劃問題，矩陣維數(shù)n的范圍取為100～12 000，最終時間結(jié)果是50次實驗的平均值。圖2、3分別為本文協(xié)議與Zhang-Shuang協(xié)議在轉(zhuǎn)換階段和驗證階段的效率對比。實驗結(jié)果表明，對于小規(guī)模的凸二次規(guī)劃外包計算協(xié)議，兩個協(xié)議的效率相當；但是對于較大規(guī)模的外包計算協(xié)議，新協(xié)議在轉(zhuǎn)換階段和驗證階段所需時間明顯降低，效率大大提高，具有明顯優(yōu)勢。

圖2　轉(zhuǎn)換效率對比Fig.2　The efficiency comparison of transformation

圖3　驗證效率對比Fig.3　The efficiency comparison of verification

4　結(jié)論

1)提出了新的可驗證的凸二次規(guī)劃安全外包協(xié)議，既保證了數(shù)據(jù)隱私性，又實現(xiàn)了計算結(jié)果的可驗證性。

2)與已有協(xié)議相比，新協(xié)議具有高效性，用戶不需解密操作，且在轉(zhuǎn)換階段和驗證階段所需時間都有明顯減少。

3)下一步工作重點是針對本協(xié)議，給出更為嚴格的安全性證明。

[1]劉正, 張國印. 基于云計算的Web漏洞檢測分析系統(tǒng)[J]. 哈爾濱工程大學學報, 2013, 34(10): 1274-1279, 1293.

LIU Zheng, ZHANG Guoyin. The detection and analysis system for web vulnerability[J]. Journal of Harbin engineering university, 2013, 34(10): 1274-1279, 1293.

[2]CHEN Xiaofeng, HUANG Xinyi, LI Jin, et al. New algorithms for secure outsourcing of large-scale systems of linear equations[J]. IEEE transactions on information forensics and security, 2015, 10(1): 69-78.

[3]楊松濤, 馬春光. 隨機匿名的位置隱私保護方法[J]. 哈爾濱工程大學學報, 2015, 36(3): 374-378.

YANG Songtao, MA Chunguang. Random anonymity method for location privacy protection[J]. Journal of Harbin engineering university, 2015, 36(3): 374-378.

[4]馮登國, 張敏, 張妍, 等. 云計算安全研究[J]. 軟件學報, 2011, 22(1): 71-83.

FENG Dengguo, ZHANG Min, ZHANG Yan, et al. Study on cloud computing security[J]. Journal of software, 2011, 22(1): 71-83.

[5]WANG Cong, REN Kui, WANG Jia, et al. Harnessing the cloud for securely outsourcing large-scale systems of linear equations[J]. IEEE transactions on parallel and distributed systems, 2013, 24(6): 1172-1181.

[6]張鴻博, 雙鍇. 公共云平臺中凸二次規(guī)劃計算的隱私保護[EB/OL]. (2012-12-21). http://www.paper.edu.cn/releasepaper/content/201212-644.

[7]LEI Xinyu, LIAO Xiaofeng, HUANG Tingwen, et al. Achieving security, robust cheating resistance, and high-efficiency for outsourcing large matrix multiplication computation to a malicious cloud[J]. Information sciences, 2014, 280: 205-217.

[8]BOYD S, VANDENBERGHE L. Convex optimization[M]. New York: Cambridge University Press, 2004: 127-174.

[9]ATALLAH M J, PANTAZOPOULOS K N, Rice J R, et al. Secure outsourcing of scientific computations[J]. Advances in computers, 2002, 54: 215-272.

[10]GENNARO R, GENTRY C, PARNO B. Non-interactive verifiable computing: outsourcing computation to untrusted workers[M]. Berlin Heidelberg: Springer, 2010: 465-482.

[11]ZHANG Yihua, BLANTON M. Efficient secure and verifiable outsourcing of matrix multiplications[M]//CHOW S S M, CAMENISCH J, HUI L C K, et al. Information Security. Switzerland: Springer, 2014: 158-178.

[12]DURSTENFELD R. Algorithm 235: random permutation[J]. Communications of the ACM, 1964, 7(7): 420.

[13]CHEN Fei, XIANG Tao, LEI Xinyu, et al. Highly efficient linear regression outsourcing to a cloud[J]. IEEE transactions on cloud computing, 2014, 2(4): 499-508.

[14]KLINKENBERG R. Learning drifting concepts: example selection vs. example weighting[J]. Intelligent data analysis, 2004, 8(3): 281-300.

本文引用格式：

劉振華, 李賓, 白翠翠. 可驗證的凸二次規(guī)劃安全外包協(xié)議[J]. 哈爾濱工程大學學報， 2016, 37(9): 1307-1312.

LIU Zhenhua，LI Bin，BAI Cuicui. Verifiable and secure outsourcing protocol for convex quadratic programming[J]. Journal of Harbin Engineering University, 2016, 37(9): 1307-1312.

Verifiable and secure outsourcing protocol for convex quadratic programming

LIU Zhenhua1,2，LI Bin1，BAI Cuicui1

(1. School of Mathematics and Statistics, Xidian University, Xi'an 710071, China; 2. Guangxi Experiment Center of Information Science, Guilin University of Electronic Technology, Guilin 541004, China)

To reduce the computation required for resource-constrained clients when performing convex quadratic programming, we propose an outsourcing computation protocol for convex quadratic programming whose security can be verified. In the new protocol, the client first utilizes a permutation technique to transform the original problem into a new random problem, which the cloud server receives and solves, and the client then verifies the returned results. Thus, the new protocol can reduce the client's amount of required computation. Security analysis shows that the proposed protocol can protect the privacy of the input and output data, and detect any misbehavior by the cloud server to indicate the probability of a malicious model. Experimental results show that the new protocol has a comparative advantage over existing protocols in its transformation and verification efficiency.

cloud computing; convex programming; quadratic programming; outsourcing computation; privacy protection

2015-07-01.

時間：2016-07-29.

國家自然科學基金資助項目(61472470,61100229);陜西省自然科學基金資助項目(2014JM2-6091，2015JQ1007).

劉振華(1978-), 男, 教授,碩士生導師;

李賓(1990-),男,碩士研究生.

李賓, E-mail: 1654667551@qq.com.

10.11990/jheu.201507003

TN 918.1

A

1006-7043(2016)09-1307-06

網(wǎng)絡出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20160829.0827.004.html