On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography
Maxime Bombar, Nicolas Resch, Emiel Wiedijk · 2025
This work investigates the security of code-based cryptosystems such as BIKE and HQC, which are among the most promising candidates for post-quantum cryptography and rely on the hardness of decoding quasi-cyclic codes. A critical aspect of their security analysis involves understanding the distribution of elements formed by combining sparse polynomials (say with coordinates modeled as i.i.d. Bernoulli) and fixed circulant blocks. In particular, the HQC documentation models this distribution as a vector with independent coordinates and correct marginal distributions. However, we identify cases where this modeling fails, revealing that the behavior of the resulting noise is more complex than previously anticipated. While this does not invalidate the conclusion of HQC regarding the (empirically verified) Hamming weight of such elements, it does suggest that the behavior of the noise is more subtle than previously predicted. Lastly, we discuss implications of our result for potential worst-case to average-case reductions for quasi-cyclic codes.