Breaking the Hardness Assumption and IND-CPA Security of HQC Submitted to NIST PQC Project

HQC (Hamming Quasi-Cyclic) cryptosystem, proposed by Aguilar Melchor et al., is a code-based key encapsulation mechanism (KEM) running for standardization to NIST’s competition in the category “post-quantum public key encryption scheme”. The underlying hard mathematical problem of HQC is presented as the s-DQCSD (Decision Quasi-Cyclic Syndrome Decoding) problem, which refers to the question of distinguishing whether a given instance came from the s-QCSD distribution or the uniform distribution. Under the assumption that 2-DQCSD and 3-DQCSD are hard, HQC, viewed as a PKE scheme, is proven to be IND-CPA secure, and can be transformed into an IND-CCA2 secure KEM. However, in this paper, we are going to show that s-DQCSD problem is actually not intractable. More precisely, we can efficiently distinguish the s-QCSD distribution instances from the uniform distribution instances with at least a constant advantage. Furthermore, with a similar technique, we show that HQC can not attain IND-CPA security with all the proposed parameter sets.