CRYPTO READING GROUP
HAMMING QUASI CYCLIC (HQC)

Organizers: Leonardo Colò, Seunghoon Lee, Bruno Sterner
When: Friday, 10:30a.m.
Where: MC5417
Goal: Understand the KEM/PKE HQC which was recently standardised by NIST.

PROGRAM

  1. Introduction to coding theory (Seunghoon Lee, Bruno Sterner - 15/05/2026)
      - Why was it proposed?
      - Basic definitions and properties.
      - Linear codes.
      - Reed-Solomon codes.
      > References: [§2.1-2.2, 12] and [9]
  2. Introduction to Code Based Cryptography (22/05/2026)
    • - Decoding problem.
      - McEliece framework.
      - Goppa codes instantiation (overview).
      > References: [§3.1, 12]
  3. Quasi-cyclic codes (29/05/2026)
    • - Definitions and properties.
      - MDPC-McEliece scheme.
      > References: [7] and [§3.4, 12]
  4. Information Set Decoding (05/06/2026)
    • - Decoding algorithms.
      - Prange’s algorithm.
      - Stern’s algorithm.
      > References: [§5.3, 12] and [2]
  5. Decoding for quasi-cyclic codes (12/06/2026)
    • - Syndrome decoding in the quasi-cyclic setting.
      - Generic ISD vs. Structure-aware decoding approaches.
      > References: [§6.3, 4], [§3, 6], and [§5, 10]
  6. HQC KEM/PKE (19/06/2026)
    • - How doe it work?
      - Security analysis.
      > References: [1] and [4]
  7. HQC implementation and performance (26/06/2026)
    • > References: [3] and [4]
  8. Code-based signatures submitted to NIST on ramp (03/07/2026)
    • - Code-based signatures submitted to NIST on ramp: CROSS or LESS.
      - Advanced schemes building on HQC/QCC.
      - Comparison between HQC and other code based KEMs/PKEs.
      > References: [5] and [11]

RESOURCES

  1. C. Aguilar-Melchor, O. Blazy, J. -C. Deneuville, P. Gaborit and G. Zémor. Efficient Encryption From Random Quasi-Cyclic Codes. In IEEE Transactions on Information Theory, vol. 64, no. 5, pp. 3927-3943, 2018.
  2. T. Debris-Alazard. Code-based Cryptography Lecture Notes, 2023.
  3. J. Dong, Y. Hou, S. Wang, L. Sha, F. Xiao, Z. Dong, and J. Lin. HIGH: Harnessing GPU Parallelism for Optimized HQC Performance. In IACR Cryptology ePrint Archive, 2026.
  4. HQC Team. Hamming Quasi-Cyclic (HQC). NIST Submission. 2025. > Link.
  5. L. Huguenin-Dumittan and S. Vaudenay. FO-like Combiners and Hybrid Post-Quantum Cryptography. In Cryptology and Network Security: 20th International Conference, CANS 2021, pp. 225–244, 2021.
  6. C. Löndahl, T. Johansson, M. Koochak Shooshtari, M. Ahmadian-Attari, and M. Reza Aref. Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension. In Designs, Codes and Cryptography, vol. 80, pp. 359-377, 2016.
  7. R. Misoczki, J.-P. Tillich, N. Sendrier, and P.S.L.M. Barreto. MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes. In 2013 IEEE International Symposium on Information Theory. 2013.
  8. NIST. Post-Quantum Cryptography: Additional Digital Signature Schemes. > Link.
  9. R. Roth. Introduction to Coding Theory. Cambridge University Press, 2006.
  10. N. Sendrier. Decoding One Out of Many. In Post-Quantum Cryptography. PQCrypto 2011. Lecture Notes in Computer Science. vol. 7071, Springer, 2011.
  11. T. Wang, Q. Teng, A. Wang, J. Zhang, B. Pang, C. Zhao, S. Hu, and X, Wang. HARE: Compact HQC via Distance-Informed Erasure Decoding. In Cryptology ePrint Archive, 2026.
  12. V. Weger, N. Gassner, and J. Rosenthal. A Survey on Code-based Cryptography. arXiv, 2024.