Efficient Implementations of Small-Modulus Lattice KEM Components

What it is

ePrint 2026/2692 (preprint, received 30 October 2026) by Ying Liu, Yu Zhang and Xianhui Lu. It describes modulus-specific implementation work for the small-modulus lattice KEMs BAT (TCHES 2022) and END (ASIACRYPT 2026, to appear). The moduli are q=257 and q=769. The paper covers three components: public-key encoding, uniform public polynomial generation, and residual polynomial multiplication after an incomplete NTT.

How it works

Zero-selector encoding (q=257). Zero payload bytes mark the positions of ambiguous coefficients, and selector bits resolve their values. The paper analyzes selector capacity, overflow and key-generation retries. For n=1024, a 1033-byte configuration overflows with probability at most 2^-128, assuming independent uniform coefficients. Checked AVX2 decoding takes 213 cycles, against 2203 cycles for BAT's 1040-byte format.

q=769 encoding. The paper uses an existing compact radix format at the same encoded length as BAT, which lowers conversion cost.

Rejection sampling. At q=257 the sampler is specialized to simplify coefficient extraction. At q=769 it is specialized to cut random-bit demand. For (q,n)=(769,1024), expected candidate-bit demand falls 24.39% against direct 10-bit rejection. Four-polynomial generation uses 7.14-13.21% fewer AVX2 cycles.

Residual multiplication. Proven range bounds justify omitting strict input-centering corrections. Register scheduling reduces stack accesses.

Results in the full KEMs

The codecs and multiplication components were integrated into BAT and END and tested in C and AVX2.

The authors say the END AVX2 gains come mainly from the public-key codec.

Caveats

• The 2^-128 overflow bound depends on coefficients being independent and uniform.
• Decapsulation gains are much smaller than encapsulation gains, especially in AVX2 (about 5-8%).
• The page gives no code link, no benchmark platform and no constant-time or side-channel discussion, so adoption would need reimplementation and separate review.
• The 1033-byte format differs from BAT's 1040-byte key format, so it is not wire-compatible with it.