TY  - INPR
A1  - Niederreiter, Harald
A1  - Schnorr, Claus Peter
T1  - Local randomness in candidate one-way functions [Local randomness in polynomial random number and random function generators]
N2  - 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.
KW  - random number generator
KW  - random function generator
KW  - polynomial random number generator
KW  - local randomness
KW  - families of hash functions
KW  - one-way functions
Y1  - 1993
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4258
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-12282
SN  - 1095-7111
SN  - 0097-5397
N1  - 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
ER  -