Paper 2026/407 Original: eprint.iacr.org/2026/407 ↗

On the Binding Security of KEMs based on RSA and DH

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.