Reinforcing KEM (RKEM)

A reinforcing KEM (RKEM) is a generalization of KEM where encapsulation takes both a long-term public key pk_C and an ephemeral public key pk_e, producing one ciphertext that binds both. The security of pk_C is "reinforced" by pk_e — informally, breaking the scheme requires breaking both.

The motivation comes from KEM-based handshake protocols (PQ-WireGuard, KEMTLS, FSXY, SKEME/IKEv2, KEMTLS-PDK) where a server uses a client's long-term and ephemeral KEM keys together. The naïve approach — running two independent KEMs in parallel and hashing the keys together — works but is wasteful, because the ephemeral key's security requirements are weaker than the long-term key's. RKEM captures the asymmetry as a primitive.

The headline construction is Rebar (Hashimoto et al., IACR 2025/1758), a lattice-based RKEM derived from the multi-recipient adaptation of ML-KEM. Two engineering tweaks vs naïve double-ML-KEM:

• Bit-dropping on the reinforcing (ephemeral) public key — exploits the lower security requirement to compress
• Single combined ciphertext with shared randomness structure

Result: ciphertext roughly 40% smaller than two independent ML-KEM ciphertexts, while preserving CCA security via the FO transform in QROM. In PQ-WireGuard this lets the server long-term public key drop from Classic McEliece's ~261 kB to roughly 1.4 kB.

A closely related primitive, double-key KEM (2KEM), was introduced by Xue et al. earlier — but their treatment kept the two keys symmetric, so the construction reduced to "run two ML-KEMs in parallel." Beguinet et al. independently produced Maul, an asymmetric 2KEM with similar structure to Rebar, derived via a tailored FO transform rather than the standard one.

Useful beyond PQ-WireGuard for any handshake with mutual KEM-based authentication. The asymmetric-security framing is the contribution; the lattice instantiations are the deployable artifacts.

Cross-references: pq-wireguard, pq-wireguard-revisited, ml-kem, post-quantum-cryptography.