Have Your CKAKE and Eat it, Too: Efficient, Composable KEM-Authenticated Key Exchange

Myrto Arapinis; Christopher Battarbee; Mina Doosti

Paper 2026/249

Have Your CKAKE and Eat it, Too: Efficient, Composable KEM-Authenticated Key Exchange

Myrto Arapinis, University of Edinburgh

Christopher Battarbee, University of Edinburgh

Mina Doosti, University of Edinburgh

Abstract

We report on a novel authenticated key-exchange (AKE) protocol where the authentication is achieved entirely by key-encapsulation mechanisms (KEMs). Techniques to achieve AKE with KEMs have been known for some time, but have received renewed attention in a post-quantum world; in contrast to classical cryptography, the data corresponding to the NIST post-quantum KEM standard is a significant save on bandwidth compared to the signature standard. Previous KEM-authenticated AKE protocols are not known to be composable; our protocol offers similar security guarantees, plus composability, while being more efficient in terms of bandwidth compared to non-composable KEM-based AKE protocols, and composable signature-based AKE protocols. Our protocol features a modular design, and a full security proof in the Constructive Cryptography (CC) framework, one of the major composable security frameworks. We also prove the forward secrecy of our protocol, and introduce generic techniques to prove forward secrecy in CC, which may be of independent interest.

Note: fixed a formatting issue

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: authenticated key exchange post quantum cryptography provable security composable security
Contact author(s): marapini @ exseed ed ac uk
kit battarbee @ ed ac uk
mdoosti @ ed ac uk
History: 2026-02-25: revised; 2026-02-13: received; See all versions
Short URL: https://ia.cr/2026/249
License: CC BY

BibTeX

@misc{cryptoeprint:2026/249,
      author = {Myrto Arapinis and Christopher Battarbee and Mina Doosti},
      title = {Have Your {CKAKE} and Eat it, Too: Efficient, Composable {KEM}-Authenticated Key Exchange},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/249},
      year = {2026},
      url = {https://eprint.iacr.org/2026/249}
}