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

What it is

A paper (IACR ePrint 2026/2580, approved 24 October 2026, preprint) by Vincent Cheng, Zhaohui Cheng, Junfeng Fan and Kaixin Xiong. It gives a table-free version of the constant-work BCH decoder of Walters and Sinha Roy (WSR). It targets lattice KEMs that use BCH codes to cut bandwidth and decryption-failure rate.

How it works

The decoder input depends on the long-term secret and on a ciphertext the adversary may choose. Variable work, or table accesses that reveal error positions, can therefore enable key recovery even with implicit rejection. WSR's fixed-address realization avoids this by scanning the whole field for each protected lookup.

Algebraic index elimination keeps WSR's paired Berlekamp–Massey schedule. It turns each received-word-dependent selection into a fixed circuit over public addresses, so no secret-indexed table is needed. The authors prove bounded-distance correctness through radius t and source-level trace regularity.

Preconditions / Affected

The construction is instantiated on length-511 subcodes of dimension k with (k,t) = (384,14) and (320,22). The KEM results use ANSA-IBKEM1 and ANSA-IBKEM2 with the same 384-dimensional subcode. A KEM that uses a fixed-address WSR decoder is the direct comparison point.

Measured results

What to do

The compiler finding matters for anyone porting this. Ordinary C masks compiled to received-word-dependent branches under Apple Clang 21. A compiler-opaque primitive prevented this in the audited builds, so check the generated code for your own toolchain.

The authors ran mean-timing screens at the measured radii. Scalar binaries of both codes pass on x86-64, Cortex-A76 and Cortex-M4. They pass on Apple M5 only with Data Independent Timing (DIT) enabled.

Caveats

• Index elimination does not equalize operands, per the authors, so operand-dependent leakage is not addressed by the construction itself.
• The trace-regularity proof is at source level. Binary-level behavior rests on audits of specific builds and on mean-timing screens, which are weaker evidence than a full constant-time analysis.
• The page gives no code link or exact compiler flags in the abstract.