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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Keywords
Key TransparencyZero-Knowledge SetsVerifiable Random FunctionsPost-Compromise Security
Contact author(s)
antonio marcedone @ zoom us
History
2023-10-17: revised
2022-09-23: received
See all versions
Short URL
https://ia.cr/2022/1264
License
Creative Commons Attribution-NonCommercial-ShareAlike
CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2022/1264,
      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{https://eprint.iacr.org/2022/1264}},
      url = {https://eprint.iacr.org/2022/1264}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.