Paper 2021/627

Client-Auditable Verifiable Registries

Nirvan Tyagi, Ben Fisch, Joseph Bonneau, and Stefano Tessaro

Abstract

Verifiable registries allow clients to securely access a key-value mapping maintained by an untrusted server. Applications include distribution of public keys, routing information or software binaries. Existing proposals for verifiable registries rely on global invariants being audited whenever the registry is updated. Clients typically rely on trusted third-party auditors, as large registries become expensive to audit. We propose several new protocols for client-auditable registries that enable efficient verification of many updates to the registry, removing the need for third-party auditors. Our solutions use incrementally-verifiable computation (IVC) and/or RSA accumulators. Our evaluation shows that our constructions meet practical throughput requirements ($60$ updates / second), which is $100\times$ faster than naive solutions using IVC. Clients save $100$--$10^4\times$ bandwidth and computation costs over prior solutions requiring auditing every update.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. Minor revision.
Keywords
public key infrastructuretransparencyauthenticated data structuresRSA accumulatorsincrementally-verifiable computation
Contact author(s)
nirvan tyagi @ gmail com
History
2021-05-17: received
Short URL
https://ia.cr/2021/627
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/627,
      author = {Nirvan Tyagi and Ben Fisch and Joseph Bonneau and Stefano Tessaro},
      title = {Client-Auditable Verifiable Registries},
      howpublished = {Cryptology ePrint Archive, Paper 2021/627},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/627}},
      url = {https://eprint.iacr.org/2021/627}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.