X-Wing: The Hybrid KEM You’ve Been Looking For

Manuel Barbosa; Deirdre Connolly; João Diogo Duarte; Aaron Kaiser; Peter Schwabe; Karoline Varner; Bas Westerbaan

Paper 2024/039

X-Wing: The Hybrid KEM You’ve Been Looking For

Manuel Barbosa

, University of Porto, INESC TEC, Max Planck Institute for Security and Privacy

Deirdre Connolly

, SandboxAQ

João Diogo Duarte

, University of Porto, INESC TEC

Aaron Kaiser

, Max Planck Institute for Security and Privacy

Peter Schwabe

, Max Planck Institute for Security and Privacy, Radboud University Nijmegen

Karoline Varner

, Max Planck Institute for Security and Privacy, Rosenpass e.V.

Bas Westerbaan

, Cloudfare

Abstract

X-Wing is a hybrid key-encapsulation mechanism based on X25519 and ML-KEM-768. It is designed to be the sensible choice for most applications. The concrete choice of X25519 and ML-KEM-768 allows X-Wing to achieve improved efficiency compared to using a generic KEM combiner. In this paper, we introduce the X-Wing hybrid KEM construction and provide a proof of security. We show (1) that X-Wing is a classically IND-CCA secure KEM if the strong Diffie-Hellman assumption holds in the X25519 nominal group, and (2) that X-Wing is a post-quantum IND-CCA secure KEM if ML-KEM-768 is itself an IND-CCA secure KEM and SHA3-256 is secure when used as a pseudorandom function. The first result is proved in the ROM, whereas the second one holds in the standard model. Loosely speaking, this means X-Wing is secure if either X25519 or ML-KEM-768 is secure. We stress that these security gaurantees and optimizations are only possible due to the concrete choices that were made, and it may not apply in the general case.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. IACR Communications in Cryptology
DOI: 10.62056/a3qj89n4e
Keywords: Hybrid KEM Post-Quantum Cryptography Public-Key Cryptography Xwing
Contact author(s): mbb @ fc up pt
durumcrustulum @ gmail com
joao @ diogoduarte pt
aaron kaiser @ mpi-sp org
peter @ cryptojedi org
karo @ cupdev net
bas @ westerbaan name
History: 2024-04-15: last of 2 revisions; 2024-01-09: received; See all versions
Short URL: https://ia.cr/2024/039
License: CC BY

BibTeX

@misc{cryptoeprint:2024/039,
      author = {Manuel Barbosa and Deirdre Connolly and João Diogo Duarte and Aaron Kaiser and Peter Schwabe and Karoline Varner and Bas Westerbaan},
      title = {X-Wing: The Hybrid KEM You’ve Been Looking For},
      howpublished = {Cryptology ePrint Archive, Paper 2024/039},
      year = {2024},
      doi = {10.62056/a3qj89n4e},
      note = {\url{https://eprint.iacr.org/2024/039}},
      url = {https://eprint.iacr.org/2024/039}
}