Exact Bias of Linear TRNG Correctors -- Spectral Approach
For hardware security engineers designing TRNGs, this work provides precise security bounds that replace overly conservative estimates, enabling better design decisions.
This paper provides the first near-tight bias characterization for linear TRNG correctors using Fourier analysis, improving security assessments by an order of magnitude over previous estimates. It quantifies trade-offs showing that 80-bit security with 10% input bias typically requires sacrificing over 50% code rate and increased hardware cost.
Using Fourier analysis, this paper establishes near-optimal security bounds for linear correctors commonly used in True Random Number Generators (TRNGs), expressed through code weight enumerators and input bias parameters. We provide the first near-tight bias characterization in total variation, by interpolating between optimal $\ell_\infty$ and $\ell_2$ norm results. Our bounds improve security assessments by an order of magnitude over previously known (overly conservative) estimates. Across $\sim $20,000 codes, we examine fundamental trade-offs between compression efficiency, cryptographic security, and hardware complexity. Achieving 80-bit security with 10\% input bias typically requires sacrificing more than 50\% of the code rate and incurs increased hardware cost. This quantifies the inherent cost of randomness extraction in hardware TRNG implementations.