X-Wing

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

doi:10.62056/a3qj89n4e

X-Wing

The Hybrid KEM You've Been Looking For

Authors

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

Manuel Barbosa

University of Porto, Portugal
INESC TEC, Portugal
Max Planck Institute for Security and Privacy, Germany
mbb at fc dot up dot pt

Deirdre Connolly

SandboxAQ, USA
durumcrustulum at gmail dot com

João Diogo Duarte

University of Porto, Portugal
INESC TEC, Portugal
joao at diogoduarte dot pt

Aaron Kaiser

Max Planck Institute for Security and Privacy, Germany
aaron dot kaiser at mpi-sp dot org

Peter Schwabe

Max Planck Institute for Security and Privacy, Germany
Radboud University, The Netherlands
peter at cryptojedi dot org

Karolin Varner

Max Planck Institute for Security and Privacy, Germany
Rosenpass e.V., Germany
karo at cupdev dot net

Bas Westerbaan

Cloudflare, The Netherlands
bas at westerbaan dot name

Keywords: Hybrid KEM Post-Quantum Cryptography Public-Key Cryptography X-Wing

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 guarantees and optimizations are only possible due to the concrete choices that were made, and it may not apply in the general case.

References

[ABH⁺21]

Joël Alwen, Bruno Blanchet, Eduard Hauck, Eike Kiltz, Benjamin Lipp, and Doreen Riepel. Analysing the HPKE standard. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, Part I, volume 12696 of Lecture Notes in Computer Science, 87–116. Zagreb, Croatia, October 17–21, 2021. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-030-77870-5_4.

Google Scholar ePrint

[ABR01]

Michel Abdalla, Mihir Bellare, and Phillip Rogaway. The oracle Diffie-Hellman assumptions and an analysis of DHIES. In David Naccache, editor, Topics in Cryptology – CT-RSA 2001, volume 2020 of Lecture Notes in Computer Science, 143–158. San Francisco, CA, USA, April 8–12, 2001. Springer, Heidelberg, Germany. https://doi.org/10.1007/3-540-45353-9_12.

Google Scholar ePrint

[AHK⁺23]

Joël Alwen, Dominik Hartmann, Eike Kiltz, Marta Mularczyk, and Peter Schwabe. Post-Quantum Multi-Recipient Public Key Encryption. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS '23, 1108–1122. New York, NY, USA, 2023. Association for Computing Machinery. https://doi.org/10.1145/3576915.3623185.

Google Scholar ePrint

[BBLW22]

Richard Barnes, Karthikeyan Bhargavan, Benjamin Lipp, and Christopher A. Wood. Hybrid Public Key Encryption. February 2022. https://doi.org/10.17487/RFC9180.

Google Scholar ePrint

[Ber06]

Daniel J. Bernstein. Curve25519: new Diffie-Hellman speed records. In Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, editors, PKC 2006: 9th International Conference on Theory and Practice of Public Key Cryptography, volume 3958 of Lecture Notes in Computer Science, 207–228. New York, NY, USA, April 24–26, 2006. Springer, Heidelberg, Germany. https://doi.org/10.1007/11745853_14.

Google Scholar ePrint

[CDM23]

Cas Cremers, Alexander Dax, and Niklas Medinger. Keeping Up with the KEMs: Stronger Security Notions for KEMs. 2023.

Google Scholar ePrint

[CSW24]

Deirdre Connolly, Peter Schwabe, and Bas Westerbaan. X-Wing: general-purpose hybrid post-quantum KEM. 2024.

Google Scholar ePrint

[Dwo15]

Morris J. Dworkin. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. National Institute of Standards and Technology (NIST), July 2015. https://doi.org/10.6028/nist.fips.202.

Google Scholar ePrint

[GHP18]

Federico Giacon, Felix Heuer, and Bertram Poettering. KEM combiners. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018: 21st International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 10769 of Lecture Notes in Computer Science, 190–218. Rio de Janeiro, Brazil, March 25–29, 2018. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-319-76578-5_7.

Google Scholar ePrint

[LHT16]

Adam Langley, Mike Hamburg, and Sean Turner. Elliptic Curves for Security. January 2016. https://doi.org/10.17487/RFC7748.

Google Scholar ePrint

[{NIS}23]

NIST. Module-Lattice-Based Key-Encapsulation Mechanism Standard. August 2023. https://doi.org/https://doi.org/10.6028/NIST.FIPS.203.ipd.

Google Scholar ePrint

[O'B23]

Devon O'Brien. Protecting Chrome Traffic with Hybrid Kyber KEM. 2023.

Google Scholar ePrint

[OWK23]

Mike Ounsworth, Aron Wussler, and Stavros Kousidis. Combiner function for hybrid key encapsulation mechanisms (Hybrid KEMs). Internet-Draft draft-ounsworth-cfrg-kem-combiners-04, Internet Engineering Task Force, July 2023.

Google Scholar ePrint

[WR22]

Bas Westerbaan and Cefan Rubin. Defending against future threats: Cloudflare goes post-quantum. 2022.

Google Scholar ePrint

[WS23]

Bas Westerbaan and Douglas Stebila. X25519Kyber768Draft00 hybrid post-quantum key agreement. 2023.

Google Scholar ePrint

[WW23]

Bas Westerbaan and Christopher A. Wood. X25519Kyber768Draft00 hybrid post-quantum KEM for HPKE. 2023.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a3qj89n4e

History

Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09

How to cite

Manuel Barbosa, Deirdre Connolly, João Diogo Duarte, Aaron Kaiser, Peter Schwabe, Karolin Varner, and Bas Westerbaan, "X-Wing," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a3qj89n4e.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-1-21,
    author = "Barbosa, Manuel and Connolly, Deirdre and Duarte, João Diogo and Kaiser, Aaron and Schwabe, Peter and Varner, Karolin and Westerbaan, Bas",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "X-Wing",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a3qj89n4e"
}

TY - JOUR
AU - Barbosa, Manuel
AU - Connolly, Deirdre
AU - Duarte, João
AU - Kaiser, Aaron
AU - Schwabe, Peter
AU - Varner, Karolin
AU - Westerbaan, Bas
PY  - 2024
TI  - X-Wing
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 1
DO  - 10.62056/a3qj89n4e
UR  - https://doi.org/10.62056/a3qj89n4e
AB  - <p>  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 guarantees and optimizations are only possible due to the concrete choices that were made, and it may not apply in the general case. </p>
ER  -

Manuel Barbosa, Deirdre Connolly, João Diogo Duarte, Aaron Kaiser, Peter Schwabe, Karolin Varner, and Bas Westerbaan, "X-Wing," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a3qj89n4e.