On the Binding Security of KEMs based on RSA and DH

Juliane Krämer; Maximiliane Weishäupl; Stefan Winderl

Paper 2026/407

On the Binding Security of KEMs based on RSA and DH

Juliane Krämer

, University of Regensburg

Maximiliane Weishäupl, University of Regensburg

Stefan Winderl, University of Regensburg

Abstract

Motivated by new attack vectors against key encapsulation mechanisms (KEMs), a framework for binding security has recently been introduced and has since been widely used for analyzing post-quantum schemes. While the migration to such post-quantum schemes has already started, classical KEMs remain relevant due to the use of hybrid schemes, which combine post-quantum and classical KEMs. However, KEMs based on classical schemes have not been analyzed with respect to their binding security yet. Moreover, recent work revealed a connection between KEM combiners and binding security, showing that schemes for which a certain binding notion is fulfilled can be used more efficiently in combiners. In this work, we address the lack of a binding security analysis for classical KEMs and examine the implications of our results for combiners. More precisely, we consider KEMs built from classical cryptographic schemes such as Diffie-Hellman (DH) and RSA, as illustrated by NIST in SP 800-227. We cover KEMs based on (elliptic-curve) Diffie-Hellman, X25519, RSA, and RSA-OAEP. Due to structural similarities to the other DH schemes and since it has not been analyzed so far with respect to its binding security, we also include the post-quantum scheme CSIDH. Our analysis yields mixed results for the KEMs under consideration, with both binding attacks as well as proofs. Where possible, we propose minor modifications to the schemes, which improve their binding security.

Note: Revision and Restructuring of Chapter 3; Added lsb Variant for FFDH in Chapter 4

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: KEM KEM combiner binding security C2PRI Diffie-Hellman FFDH ECDH X25519 CSIDH RSA RSA-KEM RSA-OAEP
Contact author(s): juliane kraemer @ ur de
maximiliane weishaeupl @ ur de
stefan winderl @ ur de
History: 2026-06-24: last of 2 revisions; 2026-02-27: received; See all versions
Short URL: https://ia.cr/2026/407
License: CC BY

BibTeX

@misc{cryptoeprint:2026/407,
      author = {Juliane Krämer and Maximiliane Weishäupl and Stefan Winderl},
      title = {On the Binding Security of {KEMs} based on {RSA} and {DH}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/407},
      year = {2026},
      url = {https://eprint.iacr.org/2026/407}
}