Paper 2022/1264

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

Brian Chen, Zoom Video Communications
Yevgeniy Dodis, New York University
Esha Ghosh, Microsoft Research
Eli Goldin, New York University
Balachandar Kesavan, Zoom Video Communications
Antonio Marcedone, Zoom Video Communications
Merry Ember Mou, Zoom Video Communications

Key Transparency (KT) systems allow end-to-end encrypted service providers (messaging, calls, etc.) to maintain an auditable directory of their users’ public keys, producing proofs that all participants have a consistent view of those keys, and allowing each user to check updates to their own keys. KT has lately received a lot of attention, in particular its privacy preserving variants, which also ensure that users and auditors do not learn anything beyond what is necessary to use the service and keep the service provider accountable. Abstractly, the problem of building such systems reduces to constructing so-called append-only Zero-Knowledge Sets (aZKS). Unfortunately, existing aZKS (and KT) solutions do not allow to adequately restore the privacy guarantees after a server compromise, a form of Post-Compromise Security (PCS), while maintaining the auditability properties. In this work we address this concern through the formalization of an extension of aZKS called Rotatable ZKS (RZKS). In addition to providing PCS, our notion of RZKS has several other attractive features, such as a stronger (extractable) soundness notion, and the ability for a communication party with out-of-date data to efficiently “catch up” to the current epoch while ensuring that the server did not erase any of the past data. Of independent interest, we also introduce a new primitive called a Rotatable Verifiable Random Function (VRF), and show how to build RZKS in a modular fashion from a rotatable VRF, ordered accumulator, and append-only vector commitment schemes.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Key Transparency Zero-Knowledge Sets Verifiable Random Functions Post-Compromise Security
Contact author(s)
antonio marcedone @ zoom us
2022-09-26: approved
2022-09-23: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-ShareAlike


      author = {Brian Chen and Yevgeniy Dodis and Esha Ghosh and Eli Goldin and Balachandar Kesavan and Antonio Marcedone and Merry Ember Mou},
      title = {Rotatable Zero Knowledge Sets: Post Compromise Secure Auditable Dictionaries with application to Key Transparency},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1264},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.