LOCAL RANDOMNESS IN POLYNOMIAL RANDOM NUMBER AND RANDOM FUNCTION GENERATORS

A distribution on n-bit strings is called (epsilon, e)-locally random, if for every choice of e less-than-or-equal-to n positions the induce d distribution on e-bit strings is in the L(l)-norm at most epsilon aw ay 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(l),. .., f(l) be polynomials with coefficients in Z(N) =Z/NZ. The RNG that stretches a random x is-an-element-of Z(N) into the sequence of least significant bits of fl(x),...,fe(x) is studied. It is shown that this RNG provides local randomness if for every prime divisor p of N the po lynomials f(l),...,f(l) are linearly independent modulo the subspace o f polynomials of degree less-than-or-equal-to 1 in Z(p)x!. Also estab lished is local randomness in polynomial random function generators. T his yields candidates for cryptographic hash functions. The concept of local randomness in families of functions extends the concept of univ ersal families of hash functions by Carter and Wegman J. Comput. Syst em Sci., 18 (1979) pp. 143-154!. The proofs of the results rely on upp er bounds for exponential sums.