Paper 2026/1498

Multilevel Amortized Gaussian Elimination in Information-Set Decoding: Applications to HQC and PCG

Abstract

For cryptosystems whose security relies on the hardness of decoding in the sublinear regime, the best known attacks are based on Information Set Decoding (ISD). In this regime, which is particularly relevant to HQC and Pseudorandom Correlation Generators (PCG), the cost of Gaussian elimination is no longer negligible and significantly affects the overall attack complexity. In this work, we revisit the Reduce-and-Prange technique of Kim and Lee, which reduces the cost of Gaussian elimination by reusing partial pivots. We refine its complexity analysis using branching-process techniques, thereby obtaining a more accurate assessment of its performance. We then extend partial pivot reuse to Stern's algorithm and introduce MAGE-Stern, a multilevel amortized Gaussian elimination variant of Stern's algorithm. Under a consistent logic-gate cost model, MAGE-Stern improves upon the best previously known attack against HQC by approximately 3 bits in time complexity, while reducing the memory complexity by about 12 bits. In particular, we estimate the security of the standardized HQC Category I parameter set at approximately 140 bits, about 3 bits below its NIST security target. We further combine multilevel amortized Gaussian elimination with the projective decoding framework of Carrier, Hatey, and Tillich, and investigate its application to regular decoding. Applied to the reference Pseudorandom Correlation Generator (PCG) parameter sets of Boyle, Couteau, Gilboa, and Ishai, the resulting algorithms improve upon the best previously known attacks by up to 6 bits across a broad range of practical parameters.