Paper 2026/517

Multi-Instance Security Degradation of Code-Based KEMs

Abstract

The security of most prominent code-based key encapsulation mechanisms (KEMs) relies on the hardness of the syndrome decoding problem. It is well-known that in the presence of $n$ syndromes, one gets a speed-up of roughly $\sqrt n$ for decoding a single syndrome by a technique called Decoding One Out of Many (DOOM), due to Sendrier. Modern code-based schemes like HQC and BIKE work over a polynomial ring $\mathbb{F}_2[X]/(X^n-1)$ that naturally leads to $n$ syndromes. As a consequence, DOOM-type speed-ups of $\sqrt n$ have been taking into account for the HQC and BIKE parameter selection in the single-instance setting. However, we analyse a naturally appearing multi-instance setting, where the same public key is used to derive $M$ session keys $K^{(1)}, \ldots, K^{(M)}$. Our attack goal is to reconstruct a single session key $K^{(i)}$. We show that in a BIKE multi-instance setting an attacker can construct a DOOM instance with $nM$ syndromes. In an HQC and Classic McEliece multi-instance setting, an attacker obtains $M$ syndromes. Our results show that multi-instance security of code-based KEMs degrades as a function of $M$. For KEMs designed for NIST security level 1 we drop below the desired $143$ bits for a number of session keys $M \geq 2^{34}$ ($\texttt{HQC-1}$), $M \geq 2^{11}$ ($\texttt{BIKE-1}$), respectively $M \geq 2^{21}$ ($\texttt{mcecliece3488-64}$). As a conclusion, the public keys of all three code-based KEMs should be updated regularly.

Note: - Improved 1-out-of-M HQC Session Key Recovery - Updated computations