Paper 2026/2580

Table-Free Constant-Work BCH Decoding by Algebraic Index Elimination

Abstract

Algebraic error-correcting codes such as BCH let lattice-based key encapsulation mechanisms (KEMs) reduce bandwidth and the decryption-failure rate. The decoder’s input is determined jointly by the long-term secret and a ciphertext that an adversary may choose. Variable work or table accesses that reveal error positions can enable key recovery even when the KEM uses implicit rejection. Walters and Sinha Roy (WSR) gave a constant-work BCH decoder whose fixed-address realization scans the entire field per protected lookup. We introduce algebraic index elimination, a table-free realization of WSR’s paired Berlekamp–Massey schedule in which received-word-dependent selections become fixed circuits over public addresses. We prove bounded-distance correctness through radius t and source-level trace regularity for the parameterized decoder. We instantiate the construction with length-511 subcodes of dimension k , using ( k,t ) = (384 , 14) and (320 , 22). Their implementations eliminate, respectively, 5.2 and 7.2 KiB of received-word-selected field and encoder tables required by matched fixed-address WSR baselines. On WSR’s published parameter sets, an Intel i7-13700 runs the deterministic cores 35.7–82.4 × faster than the fixed-address WSR baselines. In the identity-based lattice KEMs ANSA-IBKEM1 and ANSA-IBKEM2, decapsulation is 25.5 × and 10.9 × faster than with fixed-address WSR baselines for the same 384-dimensional subcode. Index elimination does not equalize operands. Ordinary C masks compiled to received-word-dependent branches under Apple Clang 21; a compiler-opaque primitive prevented this transformation in the audited builds. At the measured radii, scalar binaries of both codes pass the x86-64, Cortex-A76 and Cortex-M4 mean-timing screens, and the Apple M5 screens with Data Independent Timing (DIT) enabled.