TY - GEN
T1 - VeRSA
T2 - 28th ACM SIGSAC Conference on Computer and Communications Security, CCS 2022
AU - Tyagi, Nirvan
AU - Fisch, Ben
AU - Zitek, Andrew
AU - Bonneau, Joseph
AU - Tessaro, Stefano
N1 - Funding Information:
Nirvan Tyagi was supported by a Facebook Graduate Research Fellowship, and part of his work took place while a visiting student at the University of Washington. Ben Fisch was funded by NSF, DARPA, and a grant from ONR. Andrew Zitek was supported by NSF grant CNS-1940713. Joseph Bonneau was supported by DARPA under Agreement HR00112020022 and NSF grant CNS-1940713. Ste-fano Tessaro was supported by NSF grants CNS-1930117 (CAREER), CNS-2026774, CNS-2154174, a JP Morgan Faculty Award, a CISCO Faculty Award, and a gift from Microsoft. Any opinions, findings and conclusions, or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the United States Government or DARPA.
Publisher Copyright:
© 2022 ACM.
PY - 2022/11/7
Y1 - 2022/11/7
N2 - 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 100x 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.
AB - 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 100x 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.
KW - authenticated data structures
KW - incrementally-verifiable computation
KW - public key infrastructure
KW - rsa accumulators
KW - transparency
UR - http://www.scopus.com/inward/record.url?scp=85143070759&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85143070759&partnerID=8YFLogxK
U2 - 10.1145/3548606.3560605
DO - 10.1145/3548606.3560605
M3 - Conference contribution
AN - SCOPUS:85143070759
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 2793
EP - 2807
BT - CCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
PB - Association for Computing Machinery
Y2 - 7 November 2022 through 11 November 2022
ER -