可验证的大规模矩阵满秩分解的安全外包

Verifiable and secure outsourcing for large matrix full rank decomposition

针对矩阵满秩分解的外包算法没有对原始矩阵中零元素的个数进行保护且没有对云返回结果的正确性进行验证的问题,提出了一个可验证的矩阵满秩分解的安全外包方案。首先,在加密阶段,结合Sherman-Morrison公式构造出一个稠密的可逆矩阵来进行加密。其次,在云计算阶段,一方面,要求云计算加密矩阵的满秩分解;另一方面,在得到满秩分解的结果(一个列满秩矩阵和一个行满秩矩阵)后,要求分别云计算列满秩矩阵的左逆和行满秩矩阵的右逆。接下来,在验证阶段,用户不仅要分别验证返回的两个矩阵是否满足行满秩和列满秩,还要验证这两个矩阵相乘是否等于加密矩阵。最后,如果验证通过,则用户可以利用私钥进行解密。在协议分析中,证明了所提方案满足正确性、安全性、高效性和可验证性。同时,当选择的原始矩阵的维度是512×512时,无论怎样改变矩阵中非零元素的密度,所提方案计算得到的加密矩阵的熵恒等于18,说明方案确实可以有效保护零元素的个数。实验结果表明所提方案具有较高的效率。

Focused on the problems of no protection for the number of zero elements in original matrix and no verification for the result returned by cloud in outsourcing algorithm of matrix full rank decomposition,a verifiable and secure outsourcing scheme of matrix full rank decomposition was proposed.Firstly,in the phase of encryption,a dense invertible matrix was constructed by using the Sherman-Morrison formula for encryption.Secondly,in the phase of cloud computing,the cloud computing of the full rank decomposition for the encryption matrix was required.And when the results of full rank decomposition for encryption matrix(a column full rank matrix and a row full rank matrix)were obtained,the cloud computing of the left inverse of the column full rank matrix and the right inverse of the row full rank matrix was required respectively.Thirdly,in the phase of verification,the client not only needed to verify whether these two matrices returned by cloud are row-full-rank or column-full-rank respectively,but also needed to verify whether the multiplication of these two matrices is equal to the encryption matrix.Finally,if the verification was passed,the client was able to use the private key to perform the decryption.In the protocol analysis,the proposed scheme is proved to satisfy correctness,security,efficiency,and verifiability.At the same time,when the dimension of the selected original matrix is 512×512,with different densities of non-zero elements in the matrix,the entropy of the encryption matrix calculated by this scheme is identically equal to 18,indicating that the scheme can protect the number of zero elements effectively.Experimental results show the effectiveness of the proposed scheme.