Computational cryptography › Public-key encryption and key exchange › Post-quantum public-key › Codes and noisy equations
Trust or structural assumption

Quasi-cyclic structure gives no shortcut

In plain words

The bet that HQC's compact, repeating code structure doesn't give attackers a shortcut.

Why it matters: If it did, HQC would weaken while decoding general codes stayed hard.

The details

On the map: no proof it is as hard as decoding a random code

HQC keeps its keys small by using quasi-cyclic codes[1, 2]: the code's structure repeats under a cyclic shift, so a whole matrix is described by a single row.

The bet is that this regularity doesn't make decoding easier. Unlike for random codes, there is no proof that decoding quasi-cyclic codes is as hard. Confidence comes from years of cryptanalysis. It is the code-based counterpart of the structured-lattice bet behind ML-KEM, and BIKE, another code-based scheme, relies on a similar structure[3].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

References

  1. Carlos Aguilar-Melchor, Olivier Blazy, Jean-Christophe Deneuville et al. Efficient Encryption From Random Quasi-Cyclic Codes. IEEE Transactions on Information Theory, 2018. doi:10.1109/tit.2018.2804444
  2. Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb and Loïc Bidoux. HQC: Hamming Quasi-Cyclic, specification. HQC team, 2025. pqc-hqc.org/doc/hqc_specifications_2025_08_22.pdf
  3. Gorjan Alagic, Maxime Bros, Pierre Ciadoux et al. Status report on the fourth round of the NIST post-quantum cryptography standardization process. National Institute of Standards and Technology (U.S.), 2025. doi:10.6028/NIST.IR.8545