Hash First, Argue Later
Dario Fiorea, Cédric Fournet Ab, Esha Ghoshc, Markulf Kohlweissb, Olga Ohrimenkob, Bryan Jeffery Parnod
- aIMDEA Software Institute, Madrid, Spain
- bMicrosoft Research, Cambridge, United Kingdom
- cBrown University, Providence, RI, USA
- dMicrosoft Research, Redmond, WA, USA
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
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.
TL;DRThis paper investigates multi- correlation hash & prove schemes for verifiable computations that operate on succinct data hashes and proposes efficient constructions that lift classes of existing arguments schemes for fixed relations to multi-relation hash& prove schemes. (Semantic Scholar)