HQC

HQC (Hamming Quasi-Cyclic) is a key encapsulation mechanism (KEM) based on code theory, and selected for standardization as a backup for ML-KEM (NIST IR 8545).

Parameters

Description of HQC parameters

Parameters	Description
\(n_1\)	The length of the Reed-Solomon code.
\(n_2\)	The length of the Reed-Muller code.
\(n\)	The length of the ambient space (smallest primitive prime greater than \(n_1 n_2\))
\(w\)	The weight of the \(n\)-dimensional vectors \(\mathbf{x}, \mathbf{y}\)
\(w_\mathbf{r} = w_\mathbf{e}\)	The weight of \(\mathbf{r}_1, \mathbf{r}_2\)

Size in bytes for HQC

Instance	Public key	Secret key	Ciphertext	Shared secret
HQC-128	2249	56	4497	64
HQC-192	4522	64	9042	64
HQC-256	7245	72	14485	64

Implementations

The reference implementation can be downloaded from the project’s page: https://pqc-hqc.org/implementation.html. There is also AVX2 and hardware optimized implementations.

HQC is integrated in Open Quantum Safe’s liboqs and in PQClean.

Attacks

The specification (version 2025/02/19) has a section on known attacks. They include:

• Attacks against Syndrome Decoding: [Pra62], [Ste89], [TS16a], [GJLondahl14], [LondahlJKS+16], [Sen11a].

• Specific structural attacks: [BJMM12], [MO15a], [MMT11a], [Dum91].

• The choice of the parameters: [BJMM12], [BLP08], [Ber10], [CC98], [FS09], [MO15b], [MMT11b], [Sen11b], [TS16b].

More recent attacks include:

• OT-PCA: New Key-Recovery Plaintext-Checking Oracle Based Side-Channel Attacks on HQC with Offline Templates [DG24].

• A New Key Recovery Side-Channel Attack on HQC with Chosen Ciphertext [GLG22]

• A New Decryption Failure Attack Against HQC [GJ20]

• Cache-Timing Attack Against HQC [HSC+23]

Bibliography

[BJMM12] (1,2)

Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer. Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, David Pointcheval, and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, volume 7237, pages 520–536. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. URL: http://link.springer.com/10.1007/978-3-642-29011-4_31 (visited on 2025-03-27), doi:10.1007/978-3-642-29011-4_31.

[Ber10]

Daniel J. Bernstein. Grover vs. McEliece. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, and Nicolas Sendrier, editors, Post-Quantum Cryptography, volume 6061, pages 73–80. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. URL: http://link.springer.com/10.1007/978-3-642-12929-2_6 (visited on 2025-03-27), doi:10.1007/978-3-642-12929-2_6.

[BLP08]

Daniel J. Bernstein, Tanja Lange, and Christiane Peters. Attacking and Defending the McEliece Cryptosystem. In Johannes Buchmann and Jintai Ding, editors, Post-Quantum Cryptography, volume 5299, pages 31–46. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. URL: http://link.springer.com/10.1007/978-3-540-88403-3_3 (visited on 2025-03-27), doi:10.1007/978-3-540-88403-3_3.

[CC98]

A. Canteaut and F. Chabaud. A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511. IEEE Transactions on Information Theory, 44(1):367–378, January 1998. URL: https://ieeexplore.ieee.org/document/651067 (visited on 2025-03-27), doi:10.1109/18.651067.

[DG24]

Haiyue Dong and Qian Guo. OT-PCA: New Key-Recovery Plaintext-Checking Oracle Based Side-Channel Attacks on HQC with Offline Templates. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025(1):251–274, December 2024. URL: https://tosc.iacr.org/index.php/TCHES/article/view/11929 (visited on 2025-03-27), doi:10.46586/tches.v2025.i1.251-274.

[Dum91]

Ilya Dumer. (PDF) On minimum distance decoding of linear codes. In ResearchGate. 1991. URL: https://www.researchgate.net/publication/296573348_On_minimum_distance_decoding_of_linear_codes (visited on 2025-03-27).

[FS09]

Matthieu Finiasz and Nicolas Sendrier. Security Bounds for the Design of Code-Based Cryptosystems. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, and Mitsuru Matsui, editors, Advances in Cryptology – ASIACRYPT 2009, volume 5912, pages 88–105. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. URL: http://link.springer.com/10.1007/978-3-642-10366-7_6 (visited on 2025-03-27), doi:10.1007/978-3-642-10366-7_6.

[GLG22]

Guillaume Goy, Antoine Loiseau, and Philippe Gaborit. A New Key Recovery Side-Channel Attack on HQC with Chosen Ciphertext. In Jung Hee Cheon and Thomas Johansson, editors, Post-Quantum Cryptography, volume 13512, pages 353–371. Springer International Publishing, Cham, 2022. URL: https://link.springer.com/10.1007/978-3-031-17234-2_17 (visited on 2025-03-27), doi:10.1007/978-3-031-17234-2_17.

[GJ20]

Qian Guo and Thomas Johansson. A New Decryption Failure Attack Against HQC. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2020, volume 12491, pages 353–382. Springer International Publishing, Cham, 2020. URL: https://link.springer.com/10.1007/978-3-030-64837-4_12 (visited on 2025-03-27), doi:10.1007/978-3-030-64837-4_12.

[GJLondahl14]

Qian Guo, Thomas Johansson, and Carl Löndahl. A New Algorithm for Solving Ring-LPN with a Reducible Polynomial. September 2014. URL: http://arxiv.org/abs/1409.0472 (visited on 2025-03-27), arXiv:1409.0472, doi:10.48550/arXiv.1409.0472.

[HSC+23]

Senyang Huang, Rui Qi Sim, Chitchanok Chuengsatiansup, Qian Guo, and Thomas Johansson. Cache-Timing Attack Against HQC. IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 136–163, June 2023. URL: https://tches.iacr.org/index.php/TCHES/article/view/10959 (visited on 2025-03-27), doi:10.46586/tches.v2023.i3.136-163.

[LondahlJKS+16]

Carl Löndahl, Thomas Johansson, Masoumeh Koochak Shooshtari, Mahmoud Ahmadian-Attari, and Mohammad Reza Aref. Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension. Designs, Codes and Cryptography, 80(2):359–377, August 2016. URL: https://doi.org/10.1007/s10623-015-0099-x (visited on 2025-03-27), doi:10.1007/s10623-015-0099-x.

[MMT11a]

Alexander May, Alexander Meurer, and Enrico Thomae. Decoding Random Linear Codes in \$\tilde\\mathcal\\vphantom \\O\vphantom \\\vphantom \\(2\textasciicircum \0.054n\)\$. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011, 107–124. Berlin, Heidelberg, 2011. Springer. doi:10.1007/978-3-642-25385-0_6.

[MMT11b]

Alexander May, Alexander Meurer, and Enrico Thomae. Decoding Random Linear Codes in \$\tilde\\mathcal\\vphantom \\O\vphantom \\\vphantom \\(2\textasciicircum \0.054n\)\$. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011, 107–124. Berlin, Heidelberg, 2011. Springer. doi:10.1007/978-3-642-25385-0_6.

[MO15a]

Alexander May and Ilya Ozerov. On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, volume 9056, pages 203–228. Springer Berlin Heidelberg, Berlin, Heidelberg, 2015. URL: http://link.springer.com/10.1007/978-3-662-46800-5_9 (visited on 2025-03-27), doi:10.1007/978-3-662-46800-5_9.

[MO15b]

Alexander May and Ilya Ozerov. On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, volume 9056, pages 203–228. Springer Berlin Heidelberg, Berlin, Heidelberg, 2015. URL: http://link.springer.com/10.1007/978-3-662-46800-5_9 (visited on 2025-03-27), doi:10.1007/978-3-662-46800-5_9.

[Pra62]

E. Prange. The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory, 8(5):5–9, September 1962. URL: https://ieeexplore.ieee.org/document/1057777 (visited on 2025-03-27), doi:10.1109/TIT.1962.1057777.

[Sen11a]

Nicolas Sendrier. Decoding One Out of Many. In Bo-Yin Yang, editor, Post-Quantum Cryptography, volume 7071, pages 51–67. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. URL: http://link.springer.com/10.1007/978-3-642-25405-5_4 (visited on 2025-03-27), doi:10.1007/978-3-642-25405-5_4.

[Sen11b]

Nicolas Sendrier. Decoding One Out of Many. In Bo-Yin Yang, editor, Post-Quantum Cryptography, volume 7071, pages 51–67. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. URL: http://link.springer.com/10.1007/978-3-642-25405-5_4 (visited on 2025-03-27), doi:10.1007/978-3-642-25405-5_4.

[Ste89]

Jacques Stern. A method for finding codewords of small weight. In Gérard Cohen and Jacques Wolfmann, editors, Coding Theory and Applications, 106–113. Berlin, Heidelberg, 1989. Springer. doi:10.1007/BFb0019850.

[TS16a]

Rodolfo Canto Torres and Nicolas Sendrier. Analysis of Information Set Decoding for a Sub-linear Error Weight. In Post-Quantum Cryptography - PQCrypto 2016. February 2016. URL: https://inria.hal.science/hal-01244886 (visited on 2025-03-27).

[TS16b]

Rodolfo Canto Torres and Nicolas Sendrier. Analysis of Information Set Decoding for a Sub-linear Error Weight. In Post-Quantum Cryptography - PQCrypto 2016. February 2016. URL: https://inria.hal.science/hal-01244886 (visited on 2025-03-27).