随着云计算的快速普及和广泛应用,如何安全高效的将繁重的计算任务外包给云服务器已经越来越受到人们的关注,尤其是那些计算资源有限的用户。本文中,我们探讨的是云计算中大型线性规划的安全外包问题。线性规划(LP)已经在科学领域的各种场景中得到了广泛的应用,比如,网络流问题、数据包路由、投资组合优化和财务数据管理等方面。对资源有限的用户来,求解大型的线性规划问题是一笔非常大的计算开销。因此,研究一种能够安全高效的大型线性规划问题的外包方案非常必要。本文主要有以下几个方面的工作:1.研究了现有的线性规划问题的外包方案,重点研究了基于转换方法的安全外包方案,总结了现有方案的不足之处。2.在完全恶意模型下,我们首次利用稀疏矩阵技术提出了一种大型线性规划的外包算法。该算法能够适用于任何类型的线性规划问题,包括有可行解、无可行解和无界等三种情况。与目前最优的算法相比(O(nρ),2<ρ≤3),我们所提出的算法只需要复杂度为O(n2)的计算开销。3.对上述三种情况,提出了完整的验证算法,它使得客户能够在计算复杂度为O(n)的情况下,以100%(最优)的概率发现云服务器的作弊行为。证明了方案在一次一密的前提下是安全的。对方案进行了效率分析和仿真实验,与Wang提出的方案相比,我们的方案是高效且实用的。