方阵幂安全外包云计算

方案，在该方案中，用户对U1和U2隐藏了模幂运算中的底数和指数，且假设U1和U2互不通信，以保证数据的隐私性；Chen等[2]针对模幂运算提出一个新的安全外包方案，与Hohenberger等[1]提出的外包方案不同的是，该算法建立在“单恶意”模型下，即U1和U2中至多有一个是恶意的；在双云模型下，Ma等[3]针对底数固定指数变化和底数变化指数固定两种情形的模幂运算，分别提出了一个高效的批量安全外包云计算协议。

关于线性问题安全外包协议的研究，其中，Wang等[4]针对大规模的线性方程组求解问题，提出了一个安全可验证的单云模型下的外包协议；对于线性规划问题，Wang等[5]提出了一个安全可行的单云模型下的外包计算协议。

关于矩阵运算安全外包的研究，Lei等[6]提出一个矩阵求逆运算的安全可验证云计算外包协议，协议中利用克罗内克（Kronecker）函数和随机置换巧妙构造密钥矩阵并完成加密，利用蒙特卡罗（Monte Carlo）验证算法验证结果的正确性，以此将加密和验证结果的复杂度均降低到O（n2）；胡杏等[7]利用盲化技术，为矩阵乘积、矩阵行列式、矩阵求逆分别设计了一个切实可行的安全可验证云计算外包协议。任晓霞等[8]也提出一个矩阵行列式安全外包协议，与文献[7]的方案相比，该方案将待外包的矩阵作为一个整体加密后外包给云端计算，而文献[7]的方案则先根据行列式按行（列）展开法则，将待外包的矩阵分成多个矩阵后分别加密，再将加密后的矩阵外包给云端计算。

在实际的科学研究和工程计算中，方阵幂均有较广泛的应用，如求解马尔可夫链问题[9]、数值方法求时滞微分方程近似解问题[10]、人口预测、经济数据分析与预测等。对于方阵幂的计算问题，邓勇[11]和王汉斌[12]均介绍了一些特殊方阵的幂运算快速计算方法，而对于一般方阵的幂运算，尚无通用的快捷之法，必须借助于计算机来完成计算。然而由于方阵幂的计算复杂度较高，当方阵阶数较大或幂数较高时，计算能力受限的用户仍不能够自己完成计算，或者自己完成此计算所需要的时间超出了可接受的范围，所以，面临此类方阵幂计算的用户必须借助于计算能力巨大的云计算平台来完成相关计算。因此为此类云用户设计一个安全的方阵幂云计算外包协议显得十分必要。

1 外包计算模型

图1是本文提出的外包云计算单云模型，模型由云用户和云服务端两个实体构成。其中：云用户有大量昂贵的方阵幂计算任务需要处理，而云服务端有海量的计算资源可供云用户使用。外包计算的具体流程为：1）用户在本地将需要外包的计算任务T进行加密，得到加密后的任务ET；2）用户将加密后的任务ET经由网络发送给云服务端；3）云服务端接收到用户发送的任务ET后，完成对任务ET的处理，得到相应的处理结果ER；4）云服务端将处理结果ER返回给用户；5）用户接收到云服务端返回的处理结果ER后，对ER进行解密，得到解密后的结果R；6）验证R的正确性，若正确则接受服务端返回的结果ER，且原任务T的正确结果即为R，否则拒绝服务端返回的结果ER。

正确性

只要用户和云端均严格按照外包协议来工作，则任务定能被云端正确处理，用户最终能够得到原任务的正确结果。

安全性

协议安全性包含输入安全和输出安全两个方面。输入安全是指协议能够保护原任务的私有性，即云端无法从接收到的加密后的任务信息中知晓原任务的具体内容；输出安全是指云端无法从加密任务的处理结果中获取原任务的正确结果。

可验证性

一个诚信的云端返回的正确结果一定能通过用户的验证，并被用户接受；云端返回的任何不正确的结果均不能被用户验证通过。

高效性

协议中用户总的计算总量须大大小于用户自身完成任务处理时的计算总量；同时，云端处理加密后任务的工作总量应该与处理原任务的工作量相近，即加密过程没有大幅增加任务处理的复杂度。

②对于每个随机整数对（r，c），计算与之对应的验证元素er，c=A（r，：）AA…Am-2个A（：，c），即Am中第r行c列元素的值。其中，等式右边的计算顺序为从左往右依次计算，具体为A（r，：）依次左乘方阵A，共循环m-2次，所得结果再左乘A（：，c）。此计算由用户自身完成，因此用户认为此结果是正确可靠的，无需再验证其正确性。

③对于l个不同的e（r，c），由用户判断是否均满足er，c=R（r，c）。若均满足，则接受云端结果，解密所得R为Am的正确结果；否则，拒绝云端返回的结果。

3.4 协议证明

定义1 如果用户和云端均严格遵守协议要求完成相关计算任务，最终用户定能得到任务Am的正确结果，则称协议SMP是一个正确的方阵幂外包计算协议。

定理1 单云模型下，协议SMP是一个正确的方阵幂外包计算协议。

证明 如协议中所述，云端接收的方阵为X=PAP-1， 则云端计算得到的R′=（X）m=PAmP-1，因此只要云端严格按照协议要求完成计算，则经用户解密后的结果R=P-1R′P=Am，即为用户所求。故SMP协议是一个正确的方阵幂外包计算协议。

定义2 如果云端不能从其已知的信息（包括矩阵X，次数m和结果R′）中破译出原始矩阵A或任务最终结果R，则称协议SMP是一个安全的方阵幂外包计算协议。

定理2 单云模型下，协议SMP是一个安全的方阵幂外包计算协议。

证明 如果云服务端试图获取原方阵A的内容，则需要从已知的方阵X中破译出P或P-1；如果试图获取最终的结果R，亦需要从R′中破译出P或P-1。由于随机置换π有n！种可能，集合α有（κα）n种可能，因此成功破译P或P-1的概率小于[n！（κα）n]-1，而外包计算时方阵阶数n通常较大，故云服务端成功获取原方阵A或最终结果R的概率几乎为零。因此，SMP协议是一个安全性的方阵幂外包计算协议。

定义3 如果用户能够准确接受云端返回的正确结果，精确识别云端返回的错误结果，并拒绝此错误结果，则称协议SMP是一个可验证的方阵幂外包计算协议。

定理3 单云模型下，协议SMP是一个可验证的方阵幂外包计算协议。

证明 1）如果云服务端返回正确结果，则用户随机选取l个元素进行验证时，一定都满足验证条件er，c=R（r，c），因此解密所得结果R将被用户接受。

2） 无论云服务端是为了谋取更多的利益而返回一个任意的结果，还是因为发生故障而返回一个错误的结果，对于字长为w位的系统，用户随机选取l个结果元素进行验证时，此结果被用户验证通过并接受的概率仅为2-wl，而目前64位系统越来越普及，且参数l的取值至少为2，因此有（2-wl≤2-128），此概率几乎为零，即用户接受一个错误结果的概率几乎为零。

综合1）和2）可得，SMP协议是一个可验证的方阵幂外包计算协议。

定义4 与用户自身完成计算相比，如果此协议能够大幅降低用户的计算复杂度，同时，与计算原任务Am相比，计算加密后的任务Xm的复杂度没有明显增加，则称议SMP是一个高效的方阵幂外包计算协议。

定理4 单云模型下，协议SMP是一个高效的方阵幂外包计算协议。

证明 根据Williams[15]的研究，矩阵乘法运算的时间复杂度最低能够达到O（n2.373）左右，因此对于方阵幂Am的计算问题，其时间复杂度约为O（（m-1）n2.373）。而本文设计的SMP协议中用户端各个阶段的时间复杂度具体为：产生密钥的时间复杂度为O（2n2+ts），其中ts为构造随机置换和非零随机数集合的线性时间；加密环节的时间复杂度为O（n2），解密环节的时间复杂度为O（n2），验证环节的时间复杂度为O（l（（m-2）n2+n）+l）；故用户总的时间复杂度为O（（l（m-2）+4）n2+ln+l+ts）。因此，对于用户来说，相对于自身计算Am，外包方式下确实降低了用户总计算量的数量级。同时，对于云端来说，计算Xm与计算Am的复杂度均为O（（m-1）n2.373），因而加密过程没有增加问题处理的复杂度。所以SMP协议是一个高效的方阵幂外包计算协议。

4 仿真实验及结果分析

4.1 实验背景

为了验证SMP协议的可行性，并评估其实际性能，研究中利用Matlab对SMP协议进行了仿真。仿真主要测算了协议方式下用户和云端各自的时间消耗，以及用户自身完成Am计算时的时间消耗。

仿真实验针对方阵阶数n固定、次数m变化，和方阵阶数n变化、次数m固定这两种情形分别进行了仿真。两种情形下的结果验证环节，参数l均取值为2，即随机选择2个校验元素来校验解密后的结果。

仿真实验的实验环境为：Inter Core i370 2.4GHz CPU，4GB内存（2.5GB可用）；Windows 7（32位）操作系统（Windows经典主题），Matlab 2007a。

实验结果分析：由表1可知，在方阵阶数n固定时，随着幂指数m的增大，外包计算的加速比也随之增大；由表2可知，在幂指数m固定时，随着方阵阶数n的增大，外包计算的加速比也随之增大。由此可见，方阵阶数越大，幂指数越高，方阵幂云计算外包的效果越好。同时，由表1和表2可知，两种情形下的效率均趋近于1，这说明加密过程没有明显增加任务处理的复杂度。因此，此方阵幂云计算外包协议具有较好的性能，达到了外包的预期目标。

5 结语

本文利用云计算平台，针对计算能力有限的对象（用户）所面临的大维数方阵的高次幂计算问题，提出了一个安全可验证的云计算外包协议，在解决大维数方阵高次幂计算问题的同时，也保证了外包方阵中数据的安全性和云服务端返回结果的可验证性，以使得此类用户可以放心地将方阵幂计算问题外包给云服务端来完成。而仿真实验表明，此协议确实达到了大幅减小用户计算量的目的。对于此项研究，如果能够找到一种更高效的验证结果正确性的方法，进一步降低用户的计算量，则外包计算的效果会更加明显，能够获得更高的加速比。

参考文献：

[1]HOHENBERGER S， LYSYANSKAYA A. How to securely outsource cryptographic computations [C]// TCC 2005： Proceedings of the Second Theory of Cryptography Conference， LNCS 3378. Berlin： Springer， 2005： 264-282.

[2]CHEN X， LI J， MA J， et al. New algorithms for secure outsourcing of modular exponentiations [C]// ESORICS 2012： Proceedings of the 17th European Symposium on Research in Computer Security， LNCS 7459. Berlin： Springer， 2012： 541-556.

[3]MA X， LI J， ZHANG F. Efficient and secure batch exponentiations outsourcing in cloud computing [C]// ICINCoS 2012： Proceedings of the 2012 4th International Conference on Intelligent Networking and Collaborative Systems. Piscataway： IEEE， 2012： 600-605.

[4]WANG C， REN K， WANG J. Harnessing the cloud for securely solving largescale systems of linear equations [C]// ICDCS 2011： Proceedings of the 2011 31st International Conference on Distributed Computing Systems. Piscataway： IEEE， 2011： 549-558.

[5]WANG C， REN K， WANG J. Secure and practical outsourcing of linear programming in cloud computing [C]// INFOCOM 2011： Proceedings of the 30th IEEE International Conference on Computer Communications. Piscataway： IEEE， 2011： 820-828.

[6]LEI X， LIAO X， HUANG T， et al. Outsourcing large matrix inversion computation to a public cloud [J]. IEEE Transactions on Cloud Computing， 2013， 1（1）： 78-87.

[7]HU X， PEI D， TANG C. Verifiable and secure outsourcing of matrix calculation and its application [J]. Scientia Sinica Informationis， 2013， 43（7）： 842-852.（胡杏，裴定一，唐春明.可验证安全外包矩阵计算及其应用[J].中国科学：信息科学，2013，43（7）：842-852.）

[8]REN X， HUANG H. Secure and efficient protocol for outsourcing large matrix determinant computation to semihonest cloud [J]. Computer Engineering and Applications， 2014， 50（10）：82-86. （任晓霞，黄宏宇. 安全高效的大矩阵行列式计算云外包协议[J]. 计算机工程与应用，2014，50（10）：82-86.）

[9]ZHANG M. Markov chain based on square matrix of factorial power [J]. Journal of Beijing Institute of Graphic Communication， 2009， 17（6）： 71-73.（张梅荣. 基于方阵乘幂的马尔可夫链问题研究[J]. 北京印刷学院学报， 2009， 17（6）： 71-73.）

[10]FORD N J， LUMB P M. Mixedtype functional differential equations： a numerical approach [J]. Journal of Computational and Applied Mathematics， 2009， 229（2）： 471-479.

[11]DENG Y. A note on the square matrix high power calculation methods [J]. College Mathematics， 2010， 26（4）： 153-156. （邓勇.关于方阵高次幂计算方法的一个注记[J]. 大学数学，2010，26（4）：153-156.）

[12]WANG H. Several kinds of solutions about the highpower of square matrix [J]. Journal of Anqing Teachers College： Natural Science Edition， 2008， 14（4）： 70-72.（王汉斌. 方阵高次幂的几种解法[J]. 安庆师范学院学报：自然科学版，2008，14（4）： 70-72.）

[13]BRUALDI R A. Introductory combinatorics [M]. 5th ed. Beijing： China Machine Press， 2012：330-337. （BRUALDI R A. 组合数学[M].冯速，译.5版.北京：机械工业出版社， 2012：330-337.）

[14]ZHOU W. Theory of numbers， groups and finite fields [M]. Beijing： Tsinghua University Press， 2013： 3-8. （周炜. 数论、群论、有限域[M]. 北京：清华大学出版社，2013：3-8.）

[15]WILLIAMS V V. Multiplying matrices faster than coppersmithwinograd [C]// STOC 2012： Proceedings of the 2012 44th Annual ACM Symposium on Theory of Computing. New York： ACM， 2012： 887-898.