【作者】 刘丽；

【导师】 吴宏锋；

【作者基本信息】 北方工业大学 ， 数学， 2023， 硕士

【摘要】 求解线性方程组不仅是数值计算中的基本问题,也是工程应用中的重要问题。随着科学技术的飞速发展和数据量的激增,越来越多的用户因自身的计算资源受限,将计算问题外包到资源丰富的云服务器,这种新的计算模式就是云计算中的外包计算。然而,用户利用这种模式提高效率的同时,往往伴随着隐私数据的泄露,甚至计算结果的正确性也不能保证。针对上述问题,本文分别基于初等矩阵、数据分割技术、奇异值分解和最优化理论研究了求解线性方程组的安全外包计算协议,主要的研究成果如下:(1)基于初等矩阵的外包计算协议。该计算协议研究了逆矩阵法求解线性方程组时用到的矩阵求逆和矩阵乘法这两种运算,使得利用逆矩阵法时,保证这两种运算的安全高效也就保证了求解线性方程组的安全高效。在计算协议中,不仅通过随机置换矩阵重新排列矩阵元素并改变非零元的大小,还为了隐藏零元素引入Sherman-Morrison公式。将盲化后的原始矩阵发送到云端,用户既可以实现快速运算,又能保证数据的隐私性,还可以验证结果的正确性。(2)基于数据分割的外包计算协议。该计算协议首先对线性方程组Ax(28)b中的系数矩阵A进行数据分割,代入原方程组生成一个同解方程组A’x(28)b’。之后对A’x(28)b’进行初等行变换,再对向量b’进行数据分割,至此,原方程组盲化为两个全新的线性方程组。用户将盲化后的方程组发送给两个不共谋的云服务器,再对返回的结果分别进行验证,保证了外包计算安全高效可验证的设计目标。此外,与之前的研究成果相比,该协议没有加大用户的计算复杂度。(3)基于奇异值分解和最优化理论的求解超定线性方程组的外包计算协议。该计算协议将求解超定线性方程组的问题转化为最优化理论问题,通过大于0的实数和稀疏三角矩阵对超定线性方程组的系数矩阵A进行盲化,再对云端返回盲化矩阵的奇异值分解进行验证,最后求解超定方程组最小二乘解并解盲化,保证了外包计算的安全性、高效性和可验证,达到了外包计算的设计目标。更多还原

【Abstract】 Solving a system of linear equations is not only a fundamental problem in numerical computation,but also an important problem in engineering applications.With the rapid development of science and technology and the proliferation of data volume,more and more users outsource their computational problems to resource-rich cloud servers due to their own limited computing resources,and this new computing model is the outsourced computing in cloud computing.However,while users use this model to improve efficiency,it is often accompanied by leakage of private data,and even the correctness of calculation results cannot be guaranteed.To address the above problems,this paper investigates a secure outsourcing computational protocol for solving systems of linear equations based on elementary matrices,data partitioning techniques,singular value decomposition and optimization theory,respectively,and the main research results are as follows:(1)An outsourcing computation protocol based on elementary matrices.This computational protocol investigates two operations,matrix inversion and matrix multiplication,used in the inverse matrix method to solve systems of linear equations,making it possible to ensure the safety and efficiency of these two operations in solving systems of linear equations when using the inverse matrix method.In the computational protocol,not only the matrix elements are rearranged and the size of non-zero elements are changed by randomly displacing the matrix,but also the Sherman-Morrison formula is introduced in order to hide the zero elements.By sending the blinded original matrix to the cloud,users can achieve fast computation while ensuring data privacy and verifying the correctness of the results.(2)Data partitioning-based outsourcing computation protocol.The protocol first partitions the coefficient matrix A of the linear equation system Ax(28)b into the original equation system to generate a homogeneous equation system A’x(28)b’.Afterwards,it performs a primary row transformation and then partitions the vector b’.Thus,the original equation system is blinded into two new linear equation systems.The user sends the blinded system of equations to two non-complicit cloud servers,and then verifies the returned results separately,ensuring the design goal of safe and efficient verification of outsourced computing.In addition,the protocol does not increase the computational complexity for the user compared to previous research results.(3)An outsourced computational protocol for solving a superdeterministic system of linear equations based on singular value decomposition and optimization theory.The computational protocol transforms the problem of solving the superdeterministic linear equation system into an optimization theory problem,blinding the coefficient matrix A of the superdeterministic linear equation system by real numbers greater than 0 and sparse triangular matrix,then verifying the singular value decomposition of the blinded matrix returned from the cloud,and finally solving the least squares solution of the superdeterministic equation system and unblinding it,which ensures the security,efficiency and verifiability of the outsourcing computation and achieves the outsourcing computation.The design goal of outsourcing computing is achieved.更多还原