Local Randomness in Polynomial Random Number and Random Function Generators
Harald Niederreiter, Claus Peter Schnorr · SIAM Journal on Computing · 1993
A distribution on n-bit strings is called $(\varepsilon ,e)$-locally random, if for every choice of $e \leqslant n$ positions the induced distribution on e-bit strings is in the $L_1 $-norm at most $\varepsilon $ away from the uniform distribution on e-bit strings. Local randomness in polynomial random number generators (RNG) that are candidate one-way functions is established. Let N be a squarefree integer and let $f_1 , \ldots ,f_\ell $ be polynomials with coefficients in $\mathbb{Z}_N = {\mathbb{Z} / {N\mathbb{Z}}}$. The RNG that stretches a random $x \in \mathbb{Z}_N $ into the sequence of least significant bits of $f_1 (x), \ldots ,f_\ell (x)$ is studied. It is shown that this RNG provides local randomness if for every prime divisor p of N the polynomials $f_1 , \ldots ,f_\ell $ are linearly independent modulo the subspace of polynomials of degree $ \leqslant 1$ in $\mathbb{Z}_p [x]$. Also established is local randomness in polynomial random function generators. This yields candidates for cryptographic hash functions. The concept of local randomness in families of functions extends the concept of universal families of hash functions by Carter and Wegman [J. Comput. System Sci., 18 (1979) pp. 143–154]. The proofs of the results rely on upper bounds for exponential sums.