Batch verifiable computation of outsourced functions
Batch verifiable computation of outsourced functions
复制标题
DOI：
10.1007/s10623-015-0092-4
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
L. Zhang;R. Safavi-Naini
中科院分区：
文献类型：
--
作者：
L. Zhang;R. Safavi-Naini
近年来，可验证的计算委托引起了人们的广泛关注，并产生了许多委托模型。在Gennaro等人的可验证计算模型中，客户端想要将函数的计算委托给云服务器。客户端生成将存储在云服务器上的函数的编码，并且具有云服务器可以在任何客户端提供的输入上计算函数以及正确性证明的属性。证明将允许客户端使用比执行计算本身少得多的时间来验证服务器计算的正确性。在所有现有的可验证计算方案中，委托函数的编码需要至少两倍于函数本身的云存储。这种对存储的严格要求在实践中可能成为瓶颈。在本文中，我们介绍了批验证计算，使多个功能的同时委托。我们构建了批量可验证计算方案，有效地减少了对云存储的要求，同时保持高效的客户端验证。为了委托函数，我们的批处理可验证计算方案只需要与函数本身一样多的云存储。我们的计划是渐近最优的云存储在这个意义上，作为。我们从一个信息理论的建设，然后引入计算假设，以获得上述效率。
Verifiable delegation of computation has attracted considerable attention in recent years and had resulted in a number of delegation models. In the verifiable computation model of Gennaro et al., a client wants to delegate the computation of a function to a cloud server. The client generates an encoding of the function that will be stored on the cloud server, and has the property that the cloud server can compute the function on any client’s supplied input together with a correctness proof. The proof will allow the client to verify the correctness of the computation by the server using substantially less time than performing the computation itself. In all existing verifiable computation schemes the encoding of the delegated function requires at least twice as much cloud storage as the function itself. This stringent requirement on storage can become a bottleneck in practice. In this paper, we introduce batch verifiable computation which enables the simultaneous delegation of multiple functions. We construct batch verifiable computation schemes that effectively reduce the requirement on cloud storage while preserving efficient client verification. To delegatefunctions, our batch verifiable computation schemes only requireas much cloud storage as thefunctions themselves. Our schemes are asymptotically optimal in terms of cloud storage in the sense thatas. We start with an information–theoretic construction and then introduce computational assumptions to obtain the above efficiencies.