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 √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 F2[X]/(Xⁿ − 1) that naturally leads to n syndromes. As a consequence, DOOM-type speed-ups of √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⁽¹⁾ , . . . , K^(M). Our attack goal is to reconstruct a single session key K⁽ⁱ⁾.

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 ≥ 2³⁴ (HQC-1), M ≥ 2¹¹ (BIKE-1), respectively M ≥ 2²¹ (mcecliece3488-64). As a conclusion, the public keys of all three code-based KEMs should be updated regularly.