Pors
Top Cited Papers
- 28 October 2007
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 2007, 584-597
- https://doi.org/10.1145/1315245.1315317
Abstract
In this paper, we define and explore proofs of retrievability (PORs). A POR scheme enables an archive or back-up service (prover) to produce a concise proof that a user (verifier) can retrieve a target file F, that is, that the archive retains and reliably transmits file data sufficient for the user to recover F in its entirety. A POR may be viewed as a kind of cryptographic proof of knowledge (POK), but one specially designed to handle a large file (or bitstring) F. We explore POR protocols here in which the communication costs, number of memory accesses for the prover, and storage requirements of the user (verifier) are small parameters essentially independent of the length of F. In addition to proposing new, practical POR constructions, we explore implementation considerations and optimizations that bear on previously explored, related schemes. In a POR, unlike a POK, neither the prover nor the verifier need actually have knowledge of F. PORs give rise to a new and unusual security definition whose formulation is another contribution of our work. We view PORs as an important tool for semi-trusted online archives. Existing cryptographic techniques help users ensure the privacy and integrity of files they retrieve. It is also natural, however, for users to want to verify that archives do not delete or modify files prior to retrieval. The goal of a POR is to accomplish these checks without users having to download the files themselves. A POR can also provide quality-of-service guarantees, i.e., show that a file is retrievable within a certain time bound.Keywords
This publication has 15 references indexed in Scilit:
- Securing distributed storagePublished by Association for Computing Machinery (ACM) ,2005
- An Oblivious Transfer Protocol with Log-Squared CommunicationLecture Notes in Computer Science, 2005
- The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge ProtocolsLecture Notes in Computer Science, 2004
- Peer-to-peer data trading to preserve informationACM Transactions on Information Systems, 2002
- An architecture for survivable coordination in large distributed systemsIEEE Transactions on Knowledge and Data Engineering, 2000
- Checking the correctness of memoriesAlgorithmica, 1994
- Efficient dispersal of information for security, load balancing, and fault toleranceJournal of the ACM, 1989
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- How to Construct Pseudorandom Permutations from Pseudorandom FunctionsSIAM Journal on Computing, 1988
- On interprocess communicationDistributed Computing, 1986