Paper 2025/1397

Starfighters—On the General Applicability of X-Wing

Abstract

In this work, we present a comprehensive analysis of QSF, the KEM combiner used by X-Wing (Communications in Cryptology 1(1), 2024). While the X-Wing paper focuses on the application of QSF to ML-KEM-768 and X25519, we discuss the combiner’s applicability to other post-quantum KEMs and ECDH instantiations. Particularly, we establish the compatibility of QSF to KEMs based on variants of the Fujisaki-Okamoto transform by proving ciphertext second-preimage resistance (C2PRI) for these variants. Building on these results, we show that QSF is compatible with, to the best of our knowledge, all post-quantum KEMs currently standardized or considered for standardization—including ML-KEM, (e)FrodoKEM, HQC, Classic McEliece, and various NTRU variants. Notably, this means these schemes can be used with QSF to construct PQ/T hybrid KEMs. In addition, we introduce QSI, a variant of QSF that combines two KEMs by hashing their shared keys, yielding a KEM that is IND-CCA-secure as long as one constituent KEM is IND-CCA-secure and the other is C2PRI-secure. We establish the same compatibility results for QSI as for QSF. Finally, we analyze both QSF and QSI regarding (their preservation of) the recently introduced family of binding properties for KEMs.

Note: Further elaboration of the QSI requirements of its component KEMs and how they apply against post-quantum and pre-quantum adversaries; cleanup in several sections without changing content; include concurrent work, elaborate on some C2PRI bounds for concrete KEMs, and update some elements of the presentation (without changing content); fix formatting of some figures; improve and clarify definitions, proofs, and presentation throughout.