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

Brian Chen, Yevgeniy Dodis, Esha Ghosh, Eli Goldin, Balachandar Kesavan, Antonio Marcedone, Merry Ember Mou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022, Proceedings
EditorsShweta Agrawal, Dongdai Lin
PublisherSpringer Science and Business Media Deutschland GmbH
Pages547-580
Number of pages34
ISBN (Print)9783031229688
DOIs
StatePublished - 2022
Event28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022 - Taipei, Taiwan, Province of China
Duration: Dec 5 2022Dec 9 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13793 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022
Country/TerritoryTaiwan, Province of China
CityTaipei
Period12/5/2212/9/22

Keywords

  • Key Transparency
  • Post-compromise security
  • Verifiable random functions
  • Zero-knowledge sets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Rotatable Zero Knowledge Sets: Post Compromise Secure Auditable Dictionaries with Application to Key Transparency'. Together they form a unique fingerprint.

Cite this