Harnessing the Cloud for Securely Outsourcing Large-Scale Systems of Linear Equations
Harnessing the Cloud for Securely Outsourcing Large-Scale Systems of Linear Equations
复制标题
DOI：
10.1109/tpds.2012.206
复制
发表时间：
2013-06
影响因子：
5.3
通讯作者：
Cong Wang-;K. Ren;Jia Wang;Qian Wang
中科院分区：
文献类型：
--
作者：
Cong Wang-;K. Ren;Jia Wang;Qian Wang
云计算经济地使计算资源有限的客户能够将大规模计算外包给云。然而，如何保护客户在计算中涉及的机密数据，然后成为一个主要的安全问题。在本文中，我们提出了一个安全的外包机制，在云中解决大型线性方程组（LE）。因为应用传统的方法，如高斯消除或LU分解（又名。直接方法）到这样的大规模LE将是昂贵的，我们通过一个完全不同的方法迭代的方法，这是更容易在实践中实现，只需要相对简单的矩阵向量运算建立安全的LE外包机制。具体来说，我们的机制使客户能够安全地利用云来迭代地找到LE解决方案的连续近似，同时保持计算的敏感输入和输出的私密性。对于鲁棒的作弊检测，我们进一步探索矩阵向量运算的代数性质，并提出了一种有效的结果验证机制，该机制允许客户以高概率在一批中验证从先前迭代近似中接收到的所有答案。在Amazon EC2上进行的安全性分析和原型实验验证了该方案的有效性和实用性。
Cloud computing economically enables customers with limited computational resources to outsource large-scale computations to the cloud. However, how to protect customers' confidential data involved in the computations then becomes a major security concern. In this paper, we present a secure outsourcing mechanism for solving large-scale systems of linear equations (LE) in cloud. Because applying traditional approaches like Gaussian elimination or LU decomposition (aka. direct method) to such large-scale LEs would be prohibitively expensive, we build the secure LE outsourcing mechanism via a completely different approach—iterative method, which is much easier to implement in practice and only demands relatively simpler matrix-vector operations. Specifically, our mechanism enables a customer to securely harness the cloud for iteratively finding successive approximations to the LE solution, while keeping both the sensitive input and output of the computation private. For robust cheating detection, we further explore the algebraic property of matrix-vector operations and propose an efficient result verification mechanism, which allows the customer to verify all answers received from previous iterative approximations in one batch with high probability. Thorough security analysis and prototype experiments on Amazon EC2 demonstrate the validity and practicality of our proposed design.