Paper 2022/1187

Strongly Anonymous Ratcheted Key Exchange

Benjamin Dowling, University of Sheffield
Eduard Hauck, Ruhr University Bochum
Doreen Riepel, Ruhr University Bochum
Paul Rösler, New York University

Anonymity is an (abstract) security goal that is especially important to threatened user groups. Therefore, widely deployed communication protocols implement various measures to hide different types of information (i.e., metadata) about their users. Before actually defining anonymity, we consider an attack vector about which targeted user groups can feel concerned: continuous, temporary exposure of their secrets. Examples for this attack vector include intentionally planted viruses on victims' devices, as well as physical access when their users are detained. Inspired by Signal's Double-Ratchet Algorithm, Ratcheted (or Continuous) Key Exchange (RKE) is a novel class of protocols that increase confidentiality and authenticity guarantees against temporary exposure of user secrets. For this, an RKE regularly renews user secrets such that the damage due to past and future exposures is minimized; this is called Post-Compromise Security and Forward-Secrecy, respectively. With this work, we are the first to leverage the strength of RKE for achieving strong anonymity guarantees under temporary exposure of user secrets. We extend existing definitions for RKE to capture attacks that interrelate ciphertexts, seen on the network, with secrets, exposed from users' devices. Although, at first glance, strong authenticity (and confidentiality) conflicts with strong anonymity, our anonymity definition is as strong as possible without diminishing other goals. We build strongly anonymity-, authenticity-, and confidentiality-preserving RKE and, along the way, develop new tools with applicability beyond our specific use-case: Updatable and Randomizable Signatures as well as Updatable and Randomizable Public Key Encryption. For both new primitives, we build efficient constructions.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Anonymity RKE CKE Ratcheted Key Exchange Continuous Key Exchange Secure Messaging State Exposure PCS FS
Contact author(s)
b dowling @ sheffield ac uk
eduard hauck @ rub de
doreen riepel @ rub de
paul roesler @ cs nyu edu
2022-09-09: approved
2022-09-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benjamin Dowling and Eduard Hauck and Doreen Riepel and Paul Rösler},
      title = {Strongly Anonymous Ratcheted Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1187},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.