International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Rotatable Zero Knowledge Sets: Post Compromise Secure Auditable Dictionaries with application to Key Transparency

Authors:
Brian Chen , Zoom
Yevgeniy Dodis , New York University
Esha Ghosh , Microsoft Research
Eli Goldin , New York University
Balachandar Kesavan , Zoom
Antonio Marcedone , Zoom
Merry Ember Mou , Zoom
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: Recently, the area of Key Transparency (KT) has received a lot of attention, as it allows the service provider to provide auditable and verifiable proofs regarding authenticity of public keys used by various participants. Moreover, it is highly preferable to do it in a privacy-preserving ways, so that users and auditors do not learn anything beyond what is necessary to keep the service provider accountable. Abstractly, the problem of building such systems reduces to constructing so called append-only Zero-Knowledge Sets (aZKS). Unfortunately, none of the previous aZKS constructions adequately addressed the problem of key rotation, which would provide Post-Compromise Security (PCS) in case the server in compromised. In this work we address this concern, and refine an extension of aZKS called Rotatable ZKS (RZKS). In addition to addressing the PCS concern, our notion of RZKS has several other attractive features, such as stronger soundness notion (called extractability), and the ability for a stale communication party to quickly catch up with the current epoch, while ensuring the the server did not erase any of the past data. Of independent interest, we also introduce and build a new primitive called Rotatable Verifiable Random Function (VRF), and show how to build RZKS in a modular fashion from rotatable VRF, ordered accumulators and append-only vector commitment schemes.
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt-2022-32584,
  title={Rotatable Zero Knowledge Sets: Post Compromise Secure Auditable Dictionaries with application to Key Transparency},
  publisher={Springer-Verlag},
  author={Brian Chen and Yevgeniy Dodis and Esha Ghosh and Eli Goldin and Balachandar Kesavan and Antonio Marcedone and Merry Ember Mou},
  year=2022
}