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, three 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.
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, three 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.”
abstract: “This handbook has been created with the highest standard of care and expertise of the parties involved. The aim of this publication is to create awareness around the urgency to start with migrations and to enhance knowledge of cryptography as an integral part of cybersecurity. Given the fact that its implementation is
highly dependent on the type of organisation that is considered and risks involved, this handbook is not
intended as a standard approach for each organisation and certain organisations might require additional
guidance and advice.
Therefore, no rights can be derived from this publication and included advice may prove to be outdated after
publication of this handbook. AIVD, CWI and TNO are under no circumstances liable for any follow-up of the
advice given in this publication”