Paper 2026/2692

Efficient Implementations of Small-Modulus Lattice KEM Components

Abstract

Small moduli support compact polynomial representations in lattice-based key encapsulation mechanisms (KEMs), including BAT (TCHES 2022) and END (ASIACRYPT 2026, to appear). However, compact encodings can be costly to convert, and uniform generation must account for both coefficient-extraction cost and random-bit demand. Incomplete number-theoretic transforms also leave residual polynomial products. To address these costs, we exploit the structure of moduli 257 and 769 to improve encoding, uniform public polynomial generation, and polynomial multiplication. At $q=257$, we introduce zero-selector encoding: zero payload bytes locate ambiguous coefficients, and selector bits resolve their values. We analyze selector capacity, overflow, and key-generation retries. For $n=1024$, a 1033-byte configuration has overflow probability at most $2^{-128}$ under independent uniform coefficients. Checked AVX2 decoding takes 213 cycles, compared with 2203 cycles for BAT's 1040-byte format. At $q=769$, we lower conversion costs using an existing compact radix format at the same encoded length as BAT. We specialize rejection sampling to simplify coefficient extraction at $q=257$ and reduce random-bit demand at $q=769$. At $(q,n)=(769,1024)$, expected candidate-bit demand decreases by 24.39\% relative to direct 10-bit rejection. Four-polynomial generation uses 7.14-13.21\% fewer AVX2 cycles. For residual multiplication, proven range bounds justify omitting strict input-centering corrections, while register scheduling reduces stack accesses. We integrate the public-key codecs and multiplication components into BAT and END. Across the tested C and AVX2 implementations, encapsulation costs decrease by $39.93-55.25\%$ in BAT and $41.36-48.84\%$ in END. The corresponding decapsulation reductions are $5.42-8.55\%$ in BAT and, for END, $23.99-45.89\%$ in C and $6.98-8.04\%$ in AVX2. END AVX2 gains mainly come from the public key codec. These results quantify the effect of modulus-specific optimizations on complete component and KEM costs.