TL;DR
This paper introduces a new "gathering property" that significantly increases decryption failure rates in BIKE, a post-quantum cryptography candidate. This property is leveraged to construct weak keys and develop two novel key recovery attacks, demonstrating a potential vulnerability in BIKE's security assumptions.
What Problem Does This Paper Address?
Post-quantum cryptography (PQC) is crucial for securing data against future quantum computers. Code-based cryptography, particularly schemes like BIKE based on Quasi-Cyclic Moderate Density Parity Check (QC-MDPC) codes, is a promising candidate due to its perceived quantum resistance. However, these schemes can suffer from decryption failures, which, if not properly understood, can leak information about the secret key. The paper addresses two critical problems: accurately estimating decryption failure rates and exploiting these failures to recover the secret key. Existing methods struggle with the complex nature of the bit-flipping decoders used in QC-MDPC.
Methods
The core innovation is the introduction of the "gathering property" for vectors. This property describes a concentration of '1's within a specific range of positions. The authors show this property is strongly linked to increased decryption failure rates.
Building on this, they propose:
- A New Construction of Weak Keys: They extend existing keys with the gathering property using ring isomorphisms to create a larger set of "weak keys" that exhibit higher decryption failure rates.
- Two Key Recovery Attacks:
- Attack 1 (No Ciphertext Reusing): This attack identifies potential weak keys by observing decryption failures. It then uses a modified Information Set Decoding (ISD) algorithm, enhanced by the gathering property, to recover the secret key.
- Attack 2 (Ciphertext Reusing Permitted): This attack is more efficient by allowing the reuse of ciphertexts. It also leverages the gathering property to identify weak keys and recover them using the modified ISD algorithm.
The paper also details a modified ISD algorithm that incorporates the gathering property as "extra information" to improve efficiency.
Datasets
Not discussed in the paper. The authors conducted simulations and experiments using BIKE's parameter sets.
Key Insights and Ideas
- The "Gathering Property" is Key: The paper establishes a direct and significant correlation between the gathering property of secret keys and errors, and increased decryption failure rates in QC-MDPC schemes. This is a novel characterization of decryption failures.
- Weak Keys Exist and Matter: The research demonstrates that a specific class of weak keys, characterized by the gathering property, leads to decryption failure rates significantly higher than the average, potentially undermining security assumptions.
- BIKE's Security Underestimated? The derived lower bound on the average decryption failure rate for BIKE (DFRavg ≥ 2⁻¹¹⁶.⁶¹) is higher than the 2⁻¹²⁸ threshold required for its d-correctness assumption, raising concerns about its claimed security level.
- Decryption Failures are Exploitable: The paper provides concrete attacks that leverage these failures to recover secret keys, demonstrating a practical threat.
- Gathering Property Enhances ISD: The gathering property acts as valuable "extra information" that can be integrated into Information Set Decoding algorithms, significantly improving their efficiency for key recovery.
Key Results
- Lower Bound on DFR: For BIKE's 128-bit security parameter set, the average decryption failure rate is shown to be DFRavg ≥ 2⁻¹¹⁶.⁶¹.
- Key Recovery Attack Complexity:
- Without ciphertext reusing: 2¹¹⁶.⁶¹
- With ciphertext reusing: 2⁹⁸.⁷⁷
These complexities are significantly lower than brute-force key search.
Limitations and Future Work
- Parameter Dependence: The analysis and attacks are primarily demonstrated for BIKE's 128-bit security parameter set. Extending these findings to other parameter sets and QC-MDPC schemes is a natural next step.
- ε Value: The paper primarily focuses on ε = 0 and 1 for the gathering property due to the complexity of probability calculations for larger ε. Investigating the impact of ε ≥ 2 on weak keys and attacks is suggested.
- Error Weight Distribution: The attacks assume a specific error weight distribution (t/2, t/2). Exploring attacks with unbalanced error weights could yield further improvements.
- Experimental Simulation Challenges: For very low decryption failure rates, experimental simulation becomes challenging. The authors suggest that for larger m, the decryption failure rate becomes extremely small, making direct simulation difficult.
- Generalization: While the attacks are demonstrated on BIKE, their applicability to other QC-MDPC based schemes is implied and warrants further investigation.
Summary updated