VeRSA: Verifiable Registries with Efficient Client Audits from RSA Authenticated Dictionaries

Nirvan Tyagi; Ben Fisch; Andrew Zitek-Estrada; Joseph Bonneau; Stefano Tessaro

Paper 2021/627

VeRSA: Verifiable Registries with Efficient Client Audits from RSA Authenticated Dictionaries

Nirvan Tyagi

, Cornell University

Ben Fisch, Yale University

Andrew Zitek-Estrada

Joseph Bonneau, New York University

Stefano Tessaro, University of Washington

Abstract

Verifiable registries allow clients to securely access a key-value mapping maintained by an untrusted server. Registries must be audited to ensure global invariants are preserved, which, in turn, allows for efficient monitoring of individual registry entries by their owners. To this end, existing proposals either assume trusted third-party auditors or rely on incrementally verifiable computation (IVC) via expensive recursive SNARKs to make registries client-auditable. In this work, we give new client-auditable verifiable registries with throughputs up to $100\times$ greater than baseline IVC solutions. Our approach relies on an authenticated dictionary based on RSA accumulators for which we develop a new constant-size invariant proof. We use this as a replacement for Merkle trees to optimize the baseline IVC approach, but also provide a novel construction which dispenses with SNARKs entirely. This latter solution adopts a new checkpointing method to ensure client view consistency.

Note: Author Name Edit: Andrew Zitek -> Andrew Zitek-Estrada

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Major revision. ACM CCS 2022
DOI: 10.1145/3548606.3560605
Keywords: public key infrastructure transparency authenticated data structures RSA accumulators incrementally-verifiable computation
Contact author(s): nirvan tyagi @ gmail com
History: 2025-11-24: last of 2 revisions; 2021-05-17: received; See all versions
Short URL: https://ia.cr/2021/627
License: CC BY

BibTeX

@misc{cryptoeprint:2021/627,
      author = {Nirvan Tyagi and Ben Fisch and Andrew Zitek-Estrada and Joseph Bonneau and Stefano Tessaro},
      title = {{VeRSA}: Verifiable Registries with Efficient Client Audits from {RSA} Authenticated Dictionaries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/627},
      year = {2021},
      doi = {10.1145/3548606.3560605},
      url = {https://eprint.iacr.org/2021/627}
}