外包模型中可验证计算的研究

发布时间：2018-03-24 15:01

本文选题：可验证计算　切入点：可验证数据库　出处：《华东师范大学》2017年硕士论文

【摘要】：随着大数据的发展进步,人们更频繁地接触到越来越多的数据。这些数据也展现出跟以往数据不同的特点:海量、异构以及劣质。资源受限的客户端无法在本地进行复杂函数计算或者存储大量数据。云计算技术的不断发展,其作为一个可满足外包计算需求且使用简单、经济的技术手段为外包计算的兴起提供了坚实的基础和动力。所谓外包计算,是指客户端将复杂的计算任务或者是较大的数据库(或数据集)外包,每次计算或问询采用付费的方式获取服务器端返回的结果。由于服务器端软硬件错误或者节约资源等,云服务器端可能会攻击外包计算,故必须保证服务器端返回结果的可验证性。可验证计算协议不仅能够保证服务器端返回结果的可验证性,并且具有以下基本性质:正确性、安全性和高效性。本文分别对计算和数据库的外包方案进行研究,主要贡献如下:(1)构造具有公开可验证性的批量可验证计算方案。本文改进现有的批量可验证计算方案,使用具有闭式效率的伪随机函数,设计出三个分别应用于外包每个单项式次数有界的多项式、每个变量次数有界的多项式和矩阵的批量可验证计算方案,这些方案均具有公开可验证性。另外,能够证明这些方案在判定线性(DLIN)假设下是安全的。此外,当函数达到京字节级别时,我们将方案进行优化,在保证效率的同时,能够减少客户端及服务器端的存储资源。(2)首次提出门限可验证数据库的概念。客户端可以将其身份及私钥秘密分享给其他多个客户端,而这些客户端可以采用门限的方式操作外包出去的数据库。现有的可验证计算方案大部分仅支持对数据库记录的修改操作,而本文提出的门限可验证数据库方案可以采用门限的方式对数据库记录执行增加、删除和修改操作。此外,我们能够证明所构造的门限可验证数据库方案在squ-CDH假设下是安全的。
[Abstract]:With big data's development and progress, more and more people are exposed to more and more data. These data also show a different feature from the previous data: massive. Heterogeneous and poor quality clients with limited resources are unable to perform complex function calculations or store large amounts of data locally. With the development of cloud computing technology, it can meet the needs of outsourced computing and is easy to use. Economic technical means provide a solid foundation and power for the rise of outsourcing computing. The so-called outsourcing computing means that clients outsource complex computing tasks or larger databases (or data sets). For each calculation or inquiry, the result returned by the server is obtained on a paid basis. Due to errors in software and hardware on the server side or resource saving, the cloud server may attack outsourced computing. Therefore, we must ensure the verifiability of the returned results on the server side. The verifiable computing protocol can not only guarantee the verifiability of the returned results on the server side, but also have the following basic properties: correctness, Security and efficiency. This paper studies the outsourced schemes of computing and database separately, and the main contributions are as follows: (1) construct a publicly verifiable batch verifiable computing scheme. In this paper, we improve the existing batch verifiable computing schemes. By using the pseudorandom function with closed efficiency, we design three computations of bounded polynomials, bounded degrees of each variable, and batch verifiability of matrices, which are respectively used to outsource the bounded degree of each monomial form. These schemes are publicly verifiable. In addition, it can be proved that these schemes are safe under the assumption of linear DLIN.Furthermore, when the function reaches the Beijing byte level, we optimize the scheme to ensure efficiency. The concept of threshold verifiable database is proposed for the first time. The client can share its identity and private key secretly with other clients. These clients can operate the outsourced database in a threshold manner. Most of the existing verifiable computing schemes only support the modification of database records. The threshold verifiable database scheme proposed in this paper can use threshold to add delete and modify database records. In addition we can prove that the proposed threshold verifiable database scheme is safe under the assumption of squ-CDH.
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP309;TP311.13

【参考文献】