PermNet-RM: Eliminating Side-Channel Leakage in HQC Reed-Muller Encoding via the GF(2) Zeta Transform

We show that encoding with the first-order Reed-Muller code RM(1,m) is algebraically identical to applying the GF(2) zeta transform to a fixed indicator vector. We exploit this equivalence to construct PermNet-RM, a Reed-Muller encoder for HQC that removes all message-dependent control flow and data access at the algorithmic level. Our encoder computes the zeta transform using a fixed-topology butterfly network made only of straight-line XOR and shift operations: no message bit influences any branch, conditional select, or memory address. The construction is ABI-compatible with reed_muller_encode() from the HQC reference implementation.

Our work is motivated by two recent attacks on HQC. Jeon et al. (ePrint 2026/071) show single-trace message recovery on ARM Cortex-M4 by exploiting leakage in the Reed-Muller encoding routine during the FO re-encryption step. Lai et al. (ePrint 2025/2162, YODO) show that ciphertext-independent timing leakages from sparse-vector processing enable passive, single-trace secret-key recovery. PermNet-RM is designed to close the specific encoder leakage that Jeon exploits.

ELMO power simulation on ARM Cortex-M0 shows that PermNet-RM reduces the mean per-bit signal amplitude by a factor of 4.6 and shrinks the leaking attack surface by a factor of 3.2 compared to BIT0MASK. On 64-bit and SIMD targets, the encoder exhibits zero timing spread across all 256 inputs, with an overhead of 1.3 cycles per encode.