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

劉振華, 李賓, 白翠翠

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

?

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

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

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

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

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

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

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

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

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

1　背景知識

1.1凸二次規(guī)劃

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

(1)

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

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

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

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

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

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

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

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

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

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

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

1.4外包計算形式化定義

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

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

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

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

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

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

1.5外包計算模型

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

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

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

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

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

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

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

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

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

2　協(xié)議描述

密鑰生成：用戶選擇兩個維隨機(jī)盲化系數(shù)向量，三個非零隨機(jī)數(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ù)生成的矩陣及隨機(jī)向量，定義私鑰SK=(M,N,J,r0,r1)。

2.1問題轉(zhuǎn)換

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

1)隱藏等式約束

為了保護(hù)向量中包含的隱私信息，用戶運(yùn)用私鑰中可逆矩陣N及維向量ri(i=0,1)，在本文中采用仿射變換將向量x映射為向量y=N-1(x+ri)，則x=Ny-ri。將x=Ny-ri代入等式Bx=d得到等式：BNy=Bri+d。為了保護(hù)輸入數(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)隱藏目標(biāo)函數(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云端解決問題

云服務(wù)器接收到新問題F0與F1，分三種情況進(jìn)行求解：

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

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

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

2.3用戶驗(yàn)證

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

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

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

(3)

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

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

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

3　協(xié)議分析

3.1安全性分析

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

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

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

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

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

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

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

與假設(shè)y為問題CQP′的最優(yōu)解矛盾。因此當(dāng)y是轉(zhuǎn)換后的凸二次規(guī)劃問題CQP′的最優(yōu)解時，y所對應(yīng)的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的隨機(jī)性保證了輸入數(shù)據(jù)b,c,d與輸出數(shù)據(jù)x的隱私性。

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

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

表1　計算量比較

3.2性能比較

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

3.3仿真實(shí)驗(yàn)

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

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

圖3　驗(yàn)證效率對比Fig.3　The efficiency comparison of verification

4　結(jié)論

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

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

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

[1]劉正, 張國印. 基于云計算的Web漏洞檢測分析系統(tǒng)[J]. 哈爾濱工程大學(xué)學(xué)報, 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ī)匿名的位置隱私保護(hù)方法[J]. 哈爾濱工程大學(xué)學(xué)報, 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]. 軟件學(xué)報, 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ī)劃計算的隱私保護(hù)[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.

本文引用格式：

劉振華, 李賓, 白翠翠. 可驗(yàn)證的凸二次規(guī)劃安全外包協(xié)議[J]. 哈爾濱工程大學(xué)學(xué)報， 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.

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

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

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

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

10.11990/jheu.201507003

TN 918.1

A

1006-7043(2016)09-1307-06

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