Exploring Decryption Failures of BIKE: New Class of Weak Keys and Key Recovery Attacks

Code-based cryptography has received a lot of attention recently because it is considered secure under quantum computing. Among them, the QC-MDPC based scheme is one of the most promising due to its excellent performance. QC-MDPC based scheme is usually subject to a small rate of decryption failure, which can leak information about the secret key. This raises two crucial problems: how to accurately estimate the decryption failure rate and how to use the failure information to recover the secret key. However, the two problems are challenging due to the difficulty of geometrically characterizing the bit-flipping decoder employed in QC-MDPC, such as using decoding radius.

In this work, we introduce the gathering property and show that it is strongly connected with the decryption failure rate of QC-MDPC. Based on the gathering property, we present two results for QC-MDPC based schemes. The first is a new construction of weak keys obtained by extending the keys that have gathering property via ring isomorphism. For the set of weak keys, we present a rigorous analysis of the probability, as well as experimental simulation of the decryption failure rates. Considering BIKE's parameter set targeting $128$-bit security, our result eventually indicates that the average decryption failure rate is lower bounded by $DFR_{avg} \ge 2^{-122.57}$. The second is a key recovery attack against CCA secure QC-MDPC schemes using decryption failures in a multi-target setting. By decrypting ciphertexts with errors satisfying the gathering property, we show that a single decryption failure can be used to identify whether a target's secret key satisfies the gathering property. Then using the gathering property as extra information, we present a modified information set decoding algorithm that efficiently retrieves the target's secret key. For BIKE's parameter set targeting $128$-bit security, a key recovery attack with complexity $2^{119.88}$ can be expected by using extrapolated decryption failure rates.