Paper 2025/018

On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography

Maxime Bombar, Centrum Wiskunde & Informatica, Institut de Mathématiques de Bordeaux
Nicolas Resch, University of Amsterdam
Emiel Wiedijk, University of Amsterdam
Abstract

Cryptography based on the presumed hardness of decoding codes -- i.e., code-based cryptography -- has recently seen increased interest due to its plausible security against quantum attackers. Notably, of the four proposals for the NIST post-quantum standardization process that were advanced to their fourth round for further review, two were code-based. The most efficient proposals -- including HQC and BIKE, the NIST submissions alluded to above -- in fact rely on the presumed hardness of decoding structured codes. Of particular relevance to our work, HQC is based on quasi-cyclic codes, which are codes generated by matrices consisting of two cyclic blocks. In particular, the security analysis of HQC requires a precise understanding of the Decryption Failure Rate (DFR), whose analysis relies on the following heuristic: given random "sparse" vectors $e_1,e_2$ (say, each coordinate is i.i.d. Bernoulli) multiplied by fixed "sparse" quasi-cyclic matrices $A_1,A_2$, the weight of resulting vector $e_1A_1+e_2A_2$ is very concentrated around its expectation. In the documentation, the authors model the distribution of $e_1A_1+e_2A_2$ as a vector with independent coordinates (and correct marginal distribution). However, we uncover cases where this modeling fails. While this does not invalidate the (empirically verified) heuristic that the weight of $e_1A_1+e_2A_2$ is concentrated, it does suggest that the behavior of the noise is a bit more subtle than previously predicted. Lastly, we also discuss implications of our result for potential worst-case to average-case reductions for quasi-cyclic codes.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
code-based cryptographyring-lpnquasi-cyclic codesworst-case to average-case reduction
Contact author(s)
maxime bombar @ math u-bordeaux fr
n a resch @ uva nl
e wiedijk @ uva nl
History
2025-01-06: approved
2025-01-05: received
See all versions
Short URL
https://ia.cr/2025/018
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/018,
      author = {Maxime Bombar and Nicolas Resch and Emiel Wiedijk},
      title = {On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/018},
      year = {2025},
      url = {https://eprint.iacr.org/2025/018}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.