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 - 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 -