Paper 2021/1263
Transparency Dictionaries with Succinct Proofs of Correct Operation
Ioanna Tzialla, Abhiram Kothapalli, Bryan Parno, and Srinath Setty
Abstract
This paper introduces Verdict, a transparency dictionary, where an untrusted service maintains a label-value map that clients can query and update (foundational infrastructure for end-to-end encryption and other applications). To prevent unauthorized modifications to the dictionary, for example, by a malicious or a compromised service provider, Verdict produces publicly-verifiable cryptographic proofs that it correctly executes both reads and authorized updates. A key advance over prior work is that Verdict produces efficiently-verifiable proofs while incurring modest proving overheads. Verdict accomplishes this by composing indexed Merkle trees (a new SNARK-friendly data structure) with Phalanx (a new SNARK that supports amortized constant-sized proofs and leverages particular workload characteristics to speed up the prover). Our experimental evaluation demonstrates that Verdict scales to dictionaries with millions of labels while imposing modest overheads on the service and clients.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- transparencySNARKsproofskey-value stores
- Contact author(s)
-
srinath @ microsoft com
it608 @ nyu edu
akothapa @ andrew cmu edu
parno @ cmu edu - History
- 2021-09-22: received
- Short URL
- https://ia.cr/2021/1263
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1263,
author = {Ioanna Tzialla and Abhiram Kothapalli and Bryan Parno and Srinath Setty},
title = {Transparency Dictionaries with Succinct Proofs of Correct Operation},
howpublished = {Cryptology ePrint Archive, Paper 2021/1263},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1263}},
url = {https://eprint.iacr.org/2021/1263}
}
