安全外包数据上的实用可验证计算研究

Cloud computing provides general users with a method of rapidly sharing a large amount of configurable computing resources via limited cost. Verifiable computation allows any user to efficiently verify the correctness of the delegated computations which were done by untrusted cloud servers. However, it is quite difficult for a verifiable computation scheme to achieve the confidentiality of user’s data, the integrity of the delegated computation and the practicality of the scheme, simultaneously. In particular, the existing verifiable computation schemes cannot essentially achieve all three properties at the same time. And so it is a strong trend in this area to design schemes that overcome the difficulty. In this project we shall study how to determine the practicality of verifiable computation schemes and find out concrete complexity requirements to measure the practicality; we shall construct practical verifiable computation schemes that achieve both the confidentiality of user’s data and the integrity of delegated computation for delegating specific functions including (but not limited to) linear functions, polynomial functions and static functions on the outsourced data; we will also implement the proposed schemes. The critical scientific problem we shall address in this project is how to choose or design suitable encryption algorithms to hide user’s data in verifiable computation, effectively combine the existing or design new verification techniques, and so achieve all three demanded properties simultaneously. The success of this project will provide good solutions to the main scientific problem and the proposed schemes will also remove the main data security concerns in applications.

云计算为普通用户提供了一种以极小的成本来快速共享大量可配置计算资源的方法。可验证计算协议可以使得用户在委托计算时对返回的计算结果实施验证以确定计算结果的正确性。在可验证计算协议中实现用户数据的机密性、委托计算的正确性以及协议的实用性是本领域的研究趋势和难点。现有的可验证计算协议无法完全同时具备上述三个特性。本项目将研究如何对可验证计算协议的实用性界定并提出具体的衡量指标，构造面向一般多项式函数的实用可验证计算协议，构造面向大规模外包数据上的统计函数计算的实用可验证计算协议，并构建公开算法集，探讨所构造协议的具体应用。本项目所要解决的关键科学问题是如何设计或选取隐藏（加密）用户数据的算法以及如何设计新型可验证计算技术或有效结合现有可验证计算技术，最终实现用户数据机密性、委托计算可验证性以及协议实用性的共存。本项目的成功实施将为上述理论课题提供解决方案，推动可验证计算技术真正走向实际应用领域。

可验证计算允许用户将计算某函数F在某输入x处的任务委托给云服务器，并以极小的成本对服务器的计算结果实施验证。现有可验证计算方案在同时实现用户数据机密性、委托计算完整性、方案实用性时存在明显不足。本项目的研究正是在上述背景下建议并展开的。在本项目执行过程中，我们针对矩阵函数、多项式函数等常用函数的委托计算问题构造了同时满足上述性质的方案，针对外包数据上的多项式函数计算问题构造了同时满足上述性质的方案，探讨了可验证计算技术在私有信息检索、属性基加密、属性基关键字搜索等具体问题中的应用，算法实现了部分所构造方案。我们针对矩阵函数构造了本领域第一批公开可委托、公开可验证的对用户输入或函数保密的方案。通过分阶段委托，上述方案可实现多项式委托计算。我们使用双层分摊的方法对现有多项式委托计算方案进行统一变换，实现了用户输入的保密性。我们设计了新的多服务器可验证计算模型，在这一模型下针对多项式函数构造了本领域第一批使用户输入得以保密的信息论安全的方案。 在这一模型下，我们实现了外包数据上的常数次多项式的信息论安全的委托计算；通过使用线性同态加密，我们实现了可外包性，显著降低了对服务器个数的需求。