可驗證的凸二次規劃安全外包協議

劉振華, 李賓, 白翠翠

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

?

可驗證的凸二次規劃安全外包協議

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

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

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

云計算；凸規劃；二次規劃；外包計算；隱私保護

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

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

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

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

1　背景知識

1.1凸二次規劃

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

(1)

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

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

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

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

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

1.2凸二次規劃對偶理論

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

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

1.3置換函數、克羅內克函數

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

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

1.4外包計算形式化定義

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

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

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

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

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

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

1.5外包計算模型

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

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

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

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

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

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

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

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

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

2　協議描述

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

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。根據生成的矩陣及隨機向量，定義私鑰SK=(M,N,J,r0,r1)。

2.1問題轉換

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

1)隱藏等式約束

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

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

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

2)隱藏不等式約束

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

3)隱藏目標函數

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

(2)

記F0=(Q′,A′,B′,b0,c0,d0)，F1=(Q′,A′,B′,b1,c1,d1)，且F0與F1為轉換后的兩個凸二次規劃問題。

2.2云端解決問題

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

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

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

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

2.3用戶驗證

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

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

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

(3)

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

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

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

3　協議分析

3.1安全性分析

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

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

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

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

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

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

即存在比y更優的解y*滿足

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

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

F0=(Q′,A′,B′,b0,c0,d0)，F1=(Q′,A′,B′,b1,c1,d1)，

另外，有以下等式成立：

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

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

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

表1　計算量比較

3.2性能比較

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

3.3仿真實驗

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

圖2　轉換效率對比Fig.2　The efficiency comparison of transformation

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

4　結論

1)提出了新的可驗證的凸二次規劃安全外包協議，既保證了數據隱私性，又實現了計算結果的可驗證性。

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

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

[1]劉正, 張國印. 基于云計算的Web漏洞檢測分析系統[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]張鴻博, 雙鍇. 公共云平臺中凸二次規劃計算的隱私保護[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.

本文引用格式：

劉振華, 李賓, 白翠翠. 可驗證的凸二次規劃安全外包協議[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

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