Paper 2026/656
Improved Codes and Decoders for HQC
, Technical University of Munich, Technical University of Munich, Technical University of MunichAbstract
The Hamming Quasi-Cyclic (HQC) cryptosystem, recently selected by NIST for standardization, uses a concatenation of Reed-Muller (RM) and Reed-Solomon (RS) codes to ensure correct decryption. This work optimizes the underlying code and decoder with the goal of reducing ciphertext and public-key sizes. First, we propose a two-level generalized concatenated code (GCC), exploiting the observation that the inner RM code contains a repetition subcode. The repetition layer incurs a smaller inner failure probability and, therefore, admits a higher code rate than the RS code. Second, we develop a reliability-based decoding framework for the outer code. The inner decoder provides a reliability measure whose distribution, jointly with the decoding outcome, is bounded analytically. These bounds allow deriving conservative DFR guarantees for two erasure-assignment strategies (threshold-based and partition-based). Combining both contributions, we observe that public-key and ciphertext sizes can be reduced by up to 4.34%.
Note: Simplified the proofs of lemmas in Section 4.3 (which also corrected a subtle error in the previous proof). Added Section 4.4 which extends the threshold-based decoder to any error weight distribution. Correspondingly updated the results table.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Code-Based CryptographyHQCHamming Quasi-CyclicGeneralized Concatenated CodeErrors-and-Erasures Decoding
- Contact author(s)
-
sebastian bitzer @ tum de
bharath purtipli @ tum de
antonia wachter-zeh @ tum de - History
- 2026-08-10: revised
- 2026-04-04: received
- See all versions
- Short URL
- https://ia.cr/2026/656
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/656,
author = {Sebastian Bitzer and Bharath Purtipli and Antonia Wachter-Zeh},
title = {Improved Codes and Decoders for {HQC}},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/656},
year = {2026},
url = {https://eprint.iacr.org/2026/656}
}
