Hash First, Argue Later: Adaptive Verifiable Computations on Outsourced Data
Hash First, Argue Later: Adaptive Verifiable Computations on Outsourced Data
复制标题
先散列，后争论：外包数据的自适应可验证计算
DOI：
10.1145/2976749.2978368
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Bryan Parno
中科院分区：
文献类型：
--
作者：
D. Fiore;C. Fournet;Esha Ghosh;Markulf Kohlweiss;O. Ohrimenko;Bryan Parno
可验证计算(VC)的证明系统有可能使云外包更值得信赖。最近的方案使有限资源的验证者能够委托大量计算，并基于简洁的参数来验证其结果：验证复杂性与输入和输出的大小(而不是计算的大小)呈线性关系。然而，云计算也往往涉及大量数据，可能会超出验证器的本地存储和I/O能力，从而限制VC的使用。本文研究了基于简洁数据散列的可验证计算的多重关系散列证明方案。因此，验证器将存储和计算委托给不受信任的工作进程。她上传数据并保存散列；与其他方交换散列；验证使用和产生散列的参数；并有选择地下载她需要访问的实际数据。符合我们定义的现有实例化要么针对有限的计算类，要么使用相对低效的技术。相反，我们提出了有效的构造，将现有的固定关系参数方案提升为多关系哈希和证明方案。我们的方案(1)依赖于在输入大小中线性运行的散列算法；(2)支持对散列输入的参数进行恒定时间验证；(3)为证明者带来最小的开销。它们的主要好处是在具有共享I/O的所有关系上摊销验证器的线性成本。具体地说，与从以前的工作中获得的解决方案相比，我们的新的散列和证明构造为验证器的1400倍的加速。我们还解释了如何通过部分外包哈希计算本身来进一步降低线性验证成本，在应用于现有VC方案时获得480倍的加速，即使是在单关系执行时也是如此。
Proof systems for verifiable computation (VC) have the potential to make cloud outsourcing more trustworthy. Recent schemes enable a verifier with limited resources to delegate large computations and verify their outcome based on succinct arguments: verification complexity is linear in the size of the inputs and outputs (not the size of the computation). However, cloud computing also often involves large amounts of data, which may exceed the local storage and I/O capabilities of the verifier, and thus limit the use of VC. In this paper, we investigate multi-relation hash & prove schemes for verifiable computations that operate on succinct data hashes. Hence, the verifier delegates both storage and computation to an untrusted worker. She uploads data and keeps hashes; exchanges hashes with other parties; verifies arguments that consume and produce hashes; and selectively downloads the actual data she needs to access. Existing instantiations that fit our definition either target restricted classes of computations or employ relatively inefficient techniques. Instead, we propose efficient constructions that lift classes of existing arguments schemes for fixed relations to multi-relation hash & prove schemes. Our schemes (1) rely on hash algorithms that run linearly in the size of the input; (2) enable constant-time verification of arguments on hashed inputs; (3) incur minimal overhead for the prover. Their main benefit is to amortize the linear cost for the verifier across all relations with shared I/O. Concretely, compared to solutions that can be obtained from prior work, our new hash & prove constructions yield a 1,400x speed-up for provers. We also explain how to further reduce the linear verification costs by partially outsourcing the hash computation itself, obtaining a 480x speed-up when applied to existing VC schemes, even on single-relation executions.