Analysis and Construction of Nonlinear Correctors Used in True Random Number Generators

The problem of true random number generators (TRNGs) traces back to von Neumann’s 1951 work that aims to simulate an unbiased coin by using a biased coin with unknown probability. The core component in a TRNG is the corrector which is a post-processing function used to reduce or eliminate statistical weaknesses of physical random number generators. Note that an ( n, m, t )-resilient function is an ( n, m, t )-corrector. Hence, a natural question is how to construct an ( n, m, t )- corrector which is not ( n, m, t )-resilient? In this paper, a framework concerning the construction of nonlinear ( n, m, t )-correctors with algebraic degree m +1 is proposed based on an equidistant linear code. We show that the derived correctors are ( n, m, t - 1)-resilient, but not ( n, m, t )-resilient. Given the importance of equidistant linear codes, we discuss how to get such a code with relatively flexible length, and how to get a pair of disjoint equidistant linear codes. In addition, the parameters comparison with linear correctors is given. It is shown that our method achieves the same correction order compared to the optimal linear method. As far as we know, the ( n, m, t )-correctors we constructed also possess the best-known correction order compared with the known nonlinear ( n,m ) resilient functions. The algebraic degrees and nonlinearities of the constructed correctors are also analyzed. Through a pair of disjoint equidistant linear codes, the nonlinearity of the nonlinear ( n, m, t )-correctors can be improved. The results show that our ( n, m, t )-correctors also possess the best algebraic degree and nonlinearity for fixed ( n,m ).