Paper 2026/2812

Constructions of Boolean Correctors with Optimal Nonlinearity and Vectorial Correctors Beyond Optimal Linear Correction Order

Abstract

Correctors are postprocessing functions that reduce or eliminate statistical bias in raw bitstreams produced by physical noise sources in true random number generators. In this paper, we develop a framework based on binary Krawtchouk polynomials for analyzing and constructing Boolean and vectorial correctors. This framework reformulates the Walsh-layer criterion into finite moment constraints on support-layer counts and preimage-layer counts. We also establish universal upper bounds on the nonlinearity of correctors, and necessary conditions on the achievable correction order. For Boolean functions, we prove that $(n-1)$-correctors are either the parity function or its complement. Then we characterize the support-layer profiles of $(n-2)$- and $(n-3)$-correctors and establish upper bounds on nonlinearity. For $n=2^k\ge 8$, a self-addressing construction yields $(n-2)$-correctors achieving the optimal nonlinearity $2^{n-1}-2^{n-1}/n$ with resiliency $n/2-2$ and algebraic degree $k+1$. Notably, this provides the first known infinite family of nonlinear correctors achieving both optimal correction order and optimal nonlinearity for that order, while having a resiliency strictly lower than the correction order. Furthermore, using constant-weight addressing, we construct $(n-d-1)$-correctors that asymptotically meet the nonlinearity upper bounds for every fixed $d\ge 1$. Our profile characterization also reveals inherent limitations of injective Maiorana--McFarland constructions at correction order $n-3$. For vectorial functions, we construct nonlinear $(s(2^m-1),m,s2^{m-1}+\ell-1)$-correctors for every $m\ge 2$ under certain conditions on $s$ and $\ell$, with resiliency at most $s2^{m-1}-2$. To the best of our knowledge, this is the first infinite family of nonlinear correctors whose correction order simultaneously exceeds that of optimal linear corrector and its own resiliency. Finally, we introduce a secondary construction that lifts these vectorial correctors to larger input dimensions while preserving their correction-order advantage. This approach yields a nonlinearity of $2^{n-1}-2^{n-n_0-1}$, where $n_0$ is the input dimension of the base corrector, along with explicit resiliency and a flexible algebraic degree.