International Association
for Cryptologic Research

Ratcheted key exchange captures the heart of modern secure messaging, wherein protocol participants continuously update their secret material to protect against full state exposure through forward security (protecting past secrets and messages) and post-compromise security (recovering from compromise). However, many practical attacks only provide the adversary with partial information about the secret state of a given party, an attack vector that has been extensively studied under the umbrella of leakage resilience. Existing models of ratcheted key exchange or messaging therefore provide less-than-optimal guarantees under partial leakage due to inherent limitations in security under full state exposure that are exacerbated by relaxations in security made by many practical protocols for performance reasons. In this work, we initiate the study of leakage-resilient ratcheted key exchange that provides typical guarantees under full state exposure and additional guarantees under partial state exposure between ratchets of the protocol. We consider unidirectional ratcheted key exchange (URKE) where one party acts as the sender and the other as receiver. Starting from the notions of Balli et al. introduced at ASIACRYPT 2020, we formalise a key indistinguishability game under randomness manipulation and bounded leakage (KIND), which in particular enables the adversary to continually leak a bounded amount of the sender's state between honest send calls. We construct a corresponding protocol from a key-updatable key encapsulation mechanism (kuKEM) and a leakage-resilient one-time MAC. By instantiating this MAC in the random oracle model (ROM), results from Balli et al. imply that in the ROM, kuKEM and KIND-secure URKE are equally powerful, i.e., can be built from each other. As a second step, given the strong limitations that key indistinguishability imposes on the adversary, we formalise a one-wayness game that also permits leakage on the receiver. We then propose a corresponding construction from leakage-resilient kuKEM, which we introduce, and a leakage-resilient one-time MAC. Furthermore, we show that leakage-resilient kuKEM and one-way-secure URKE can be built from each other in the ROM, highlighting the increased cost that strong one-way security entails. Our work opens exciting directions for developing practical, leakage-resilient messaging protocols.