可验证的凸二次规划安全外包协议

刘振华, 李宾, 白翠翠

(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