Dynamic proofs of retrievability with low server storage
Preprint
Abstract
Proofs of Retrievability (PoRs) are protocols which allow a client to store data remotely and to efficiently ensure, via audits, that the entirety of that data is still intact. A dynamic PoR system also supports efficient retrieval and update of any small portion of the data. We propose new, simple protocols for dynamic PoR that are designed for practical efficiency, trading decreased persistent storage for increased server computation, and show in fact that this tradeoff is inherent via a lower bound proof of time-space for any PoR scheme. Notably, ours is the first dynamic PoR which does not require any special encoding of the data stored on the server, meaning it can be trivially composed with any database service or with existing techniques for encryption or redundancy. Our implementation and deployment on Google Cloud Platform demonstrates our solution is scalable: for example, auditing a 1TB file takes just over 7 minutes and costs less than $0.12 USD. We also present several further enhancements, reducing the amount of client storage, or the communication bandwidth, or allowing *public verifiability*, wherein any untrusted third party may conduct an audit.Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Simple Proofs of Space-Time and Rational Proofs of Storage2019
- Proofs of Replicated Storage Without Timing Assumptions2019
- An Algebraic Framework for Pseudorandom Functions and Applications to Related-Key Security2015
- Proofs of Space: When Space Is of the Essence2014
- Verifiable Delegation of Computation over Large Datasets2011
- Proofs of Retrievability via Hardness Amplification2009
- Compact Proofs of Retrievability2008
- Fractal Merkle Tree Representation and Traversal2003
- A Digital Signature Based on a Conventional Encryption Function1988
- Fast probabilistic algorithms1979