云计算中大型线性规划问题的外包方案研究

摘要

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

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1 研究背景与意义

1.2 外包计算技术国内外研究现状

1.3 线性规划外包技术研究现状

1.4 主要贡献及内容安排

第二章 预备知识

2.1 密码学基础

2.2 安全多方计算相关定义

2.3 线性规划相关理论

2.4 外包线性规划相关理论

2.5 本章小结

第三章 线性规划外包方案研究

3.1 方案设计框架

3.2 Du等人的线性规划外包方案

3.3 Wang等人的线性规划外包方案

3.4 本章小结

第四章 高效可验证的大型线性规划外包方案

4.1 方案背景介绍

4.2 方案描述

4.3 性能比较

4.4 仿真分析

4.5 本章小结

第五章 结论与展望

5.1 研究结论

5.2 研究展望

参考文献

致谢

作者简介