Weight-64 record set for HQC-style quasi-cyclic decoding

Markku-Juhani O. Saarinen has set a new record on the quasi-cyclic syndrome decoding problem that underpins HQC, solving a public challenge instance whose error weight is 64.

The result is of direct interest for concrete security estimates of HQC, the code-based key-encapsulation mechanism still advancing through NIST's post-quantum cryptography process. Saarinen reported that luck contributed: the weight-64 error folded three times down to weight 56 on a smaller ring. HQC's ring parameters are chosen precisely to stop such trivial folding, yet he stated that updated security estimates for HQC are forthcoming from the same line of work.

The computation used a GPU-resident decoder that combined ring folding, information-set decoding with fast blockwise updates, multi-target rotations, and exact lifting back to the full ring. It ran on 24 NVIDIA GH200 GPUs at CSC's Roihu system in Finland and finished in one hour and one minute of wall-clock time (24.5 GPU-hours).

Saarinen announced the record on the NIST PQC forum.