高效低存储开销可验证外包求解大规模线性方程组方案

Efficient Verifiable Outsourcing of Solving Large-Scale Linear Equations with Low Storage Overhead

针对外包求解大规模线性方程组问题,在完全恶意模型中提出一种新的高效低存储开销可验证外包求解大规模线性方程组(efficient verifiable outsourcing of solving large-scale linear equations with low storage overhead, EVLE-LS)方案.首先利用严格对角优势矩阵和伪随机数生成器,构造了伪随机可逆稀疏矩阵生成算法.又将该算法与稀疏矩阵对稠密矩阵的编码解码过程相结合,给出了新的外包线性方程组方案.该方案只需要用户与服务器进行一轮交互,用户检测出云服务器的恶意行为的概率为1,实现完全可验证.此外,与之前已有的需要昂贵存储开销的方案相比,该方案在保证安全性的前提下将用户所需存储开销降到了常数级.最后将方案与其他3种方案进行对比,说明该方案在效率、可验证性和存储开销方面均优于已有方案.

This paper studies the secure outsourcing problem of large-scale linear equations, and proposes a new secure outsourcing scheme of large-scale linear equations in the fully malicious model. First, we construct a pseudo-random invertible sparse matrix generation algorithm involving pseudo-random number generator and the property of strictly diagonally dominant matrix. Then we combine this algorithm with the process of encoding decoding dense matrix with sparse matrix and give the new outsourcing scheme. The client in our scheme only needs 1 round interaction with the server and can detect the misbehavior of the server with an overwhelming probability (fully verifiable). In addition, compared with the previous schemes which require expensive storage overhead, our scheme reduces the overhead of storage to a constant level for the first time. We give the theoretical proof of the correctness, privacy and unforgeability of our scheme. Besides, the scheme can successfully handle the equations with no solution with enough privacy in our model. We compare the scheme with others and indicate the proposed scheme is superior to the existing ones in terms of efficiency, verifiability and storage overhead and finally provide the experimental evaluation that demonstrates the efficiency of our algorithms and the storage overhead the client needs.