Paper 2022/1264
Rotatable Zero Knowledge Sets: Post Compromise Secure Auditable Dictionaries with application to Key Transparency
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)
- 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
- 2024-11-13: last of 2 revisions
- 2022-09-23: received
- See all versions
- Short URL
- https://ia.cr/2022/1264
- License
-
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}, url = {https://eprint.iacr.org/2022/1264} }