## Local randomness in candidate one-way functions [Local randomness in polynomial random number and random function generators]

• We call a distribution on n bit strings (", e) locally random, if for every choice of e · n positions the induced distribution on e bit strings is in the L1 norm at most " away from the uniform distribution on e bit strings. We establish local randomness in polynomial random number generators (RNG) that are candidate one way functions. Let N be a squarefree integer and let f1, . . . , f be polynomials with coe±- cients in ZZN = ZZ/NZZ. We study the RNG that stretches a random x 2 ZZN into the sequence of least significant bits of f1(x), . . . , f(x). We show that this RNG provides local randomness if for every prime divisor p of N the polynomials f1, . . . , f are linearly independent modulo the subspace of polynomials of degree · 1 in ZZp[x]. We also establish 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 (1979). The proofs of our results rely on upper bounds for exponential sums.

Author: Harald Niederreiter, Claus Peter SchnorrGND urn:nbn:de:hebis:30-12282 https://doi.org/10.1137/0222045 1095-7111 0097-5397 Preprint English 1993 1993 Universitätsbibliothek Johann Christian Senckenberg 2005/07/12 families of hash functions; local randomness; one-way functions; polynomial random number generator; random function generator; random number generator 12 `Unter dem Titel "Local randomness in polynomial random number and random function generators" erschienen in: SIAM journal on computing, 22.1993, Nr. 4, S. 684-694, doi:10.1137/0222045` Publ. 1993 under the title "Local randomness in polynomial random number and random function generators", http://www.mi.informatik.uni-frankfurt.de/research/papers.html 358647312 Informatik und Mathematik / Mathematik Informatik und Mathematik / Informatik 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik 11-XX NUMBER THEORY / 11Kxx Probabilistic theory: distribution modulo 1; metric theory of algorithms / 11K06 General theory of distribution modulo 1 [See also 11J71] 11-XX NUMBER THEORY / 11Kxx Probabilistic theory: distribution modulo 1; metric theory of algorithms / 11K45 Pseudo-random numbers; Monte Carlo methods 11-XX NUMBER THEORY / 11Lxx Exponential sums and character sums (For finite fields, see 11Txx) 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section {04 in that areag 68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) / 68Qxx Theory of computing / 68Q99 None of the above, but in this section Deutsches Urheberrecht