Local Randomness in Candidate One–Way Functions

H. Niederreiter^{1} and C.P. Schnorr^{2}

1 Österreichische Akademie der Wissenschaften, Institut für Informationsverarbeitung, Sonnenfelsgasse 19, A–1010 Wien, Austria

                e-mail: nied@qiinfo.oeaw.ac.at

2 Fachbereich Mathematik / Informatik, Universität Frankfurt, Postfach 111932,

D–6000 Frankfurt/M., Germany

          e-mail: schnorr@informatik.uni-frankfurt.de

Abstract. 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 L_{1}–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 f_{1}, …, f_{ℓ} be polynomials with coefficients in ZZ_{N} = ZZ/NZZ. We study the RNG that stretches a random x ∈ ZZ_{N} into the sequence of least significant bits of f_{1}(x), …, f_{ℓ}(x). We show that this RNG provides local randomness if for every prime divisor p of N the polynomials f_{1}, …, f_{ℓ} are linearly independent modulo the subspace of polynomials of degree ≤ 1 in ZZ_{p}[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.

1 Introduction and Summary

A major open problem in cryptography is to establish one–way functions. While we cannot prove one–wayness it makes sense to analyse candidate one–way functions and to prove properties of these functions that are useful in cryptographic applications. 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 L_{1}–norm at most ε away from the uniform distribution on e–bit strings. We prove (ε, e)–local randomness for large classes of candidate one–way functions and candidate cryptographic hash functions.

We show that ℓ–tuples of polynomials (f_{1}, …, f_{ℓ}) ∈ ZZ_{N}[x]^{ℓ} with fixed coefficients in ZZ_{N} and for arbitrary odd squarefree N provide local randomness if for every prime divisor p of N the polynomials f_{1}, …, f_{ℓ} are linearly independent modulo the subspace of polynomials of degree ≤ 1 in ZZ_{p}[x]. To give an example let N be prime N > 2^{n} , let f_{1}, …, f_{ℓ} ∈ ZZ_{N}[x] be any polynomials that are linearly independent modulo the subspace of polynomials of degree ≤ 1 in ZZ_{N}[x]. We prove in Corollary 2 that for random x ∈ ZZ_{N} the bit string

(f_{1}(x)[1, …, f_{ℓ}(x)[1)

consisting of the parity bits f_{i}(x)[1 of the residues f_{i}(x) mod N in [0, N − 1] is (ε, e)–locally random provided that ε, n, ℓ and e satisfy the inequality

2^{−n/2}(2n log 2)^{e+1}2ℓ ≤ ε , (1)

where log denotes the natural logarithm. E.g. we can choose n ≥ 64, ℓ = ⌊2^{n/7}⌋, ε = 2^{−n/7}, e = ⌊n/(7 log n)⌋. Our main result comprises the case that N is an arbitrary odd squarefree integer, that the output contains several bits from each of the residues f_{i}(x) mod N, i = 1, …, ℓ, and that x is chosen to be random in a subinterval [0, M − 1] of [0, N − 1].

Note that the above function

[0, N − 1] ∋ x ↦ (f_{1}(x)[1, …, f_{ℓ}(x)[1) (2)

is a candidate one–way function. No inversion algorithm is known that is polynomial time in min(ℓ, log_{2} N). So far the one–wayness of the function (2) has only be proved for random RSA–moduli N and RSA–polynomials f_{i} = x^{e^{i}} (see below) provided that the RSA–scheme is secure. It is however possible that this one–way function is more secure than the RSA–scheme. We are not aware of any inversion algorithm which for RSA–moduli N runs in time min(2^{ℓ}, N)^{o(1)}. On the other hand the RSA–scheme can be broken by factoring N using only exp(\sqrt{log N log log N}) many steps. Is there any inversion algorithm that uses knowledge of the factorization of RSA–numbers N ? Is there any inversion algorithm that uses the structure of particular odd moduli N and of particular non–constant polynomials f_{i} ? Of course the function (2) can easily be inverted for N = 2 since f_{i}(x)[1 only depends on x[1 = x mod 2. Also the problem of inverting is trivial for constant functions as f_{i}(x) = x^{N−1}(modN) with N prime. Are there more exceptions? Almost nothing is known about the problem to invert (2). However if we cannot even find inverting algorithms for particular cases given the factorization of the modulus then this may be a sign that the function (2) is a truly one–way function.

It is important that the source of randomness in (f_{1}(x)[1, …, f_{ℓ}(x)[1) is the random argument x while the coefficients of f_{1}, …, f_{ℓ} are all fixed. Such functions are cryptographically interesting. A well known example is the random number generator (RNG) related to the RSA–scheme by Alexi, Chor, Goldreich and Schnorr (1988) and Micali, Schnorr (1991). E.g. let N be the product of two large random primes and let the integer e ≥ 3 be relatively prime to φ(N). Then the mapping

[0, N − 1] ∋ x ↦ (x^{e}[1, x^{e^{2}}[1, …, x^{ℓ}[1)

where x^{e^{i}} is taken modulo N, is a perfect (in the sense of Yao (1982) and Blum, Micali (1982)) RNG provided that the RSA–scheme is secure.

The functions x ↦ (f_{1}(x)[1, …, f_{ℓ}(x)[1) extend the class of polynomial random number generators (RNG) proposed by Micali and Schnorr (1991) which stretch a random seed x ∈ [1, N2^{−k}] into a polynomial residue P (x)(mod N). Micali and Schnorr prove that the m least significant bits of P (x)(mod N) are in the L_{1}–norm at most O(N^{−1/2}2^{k+m}(log N)^{2} deg_{N}(P)) away from the uniform distribution provided that N is prime and deg_{N}(P) ≥ 2 where deg_{N}(P) is the degree of P when P is considered modulo N.

So far local randomness has mainly been studied in functions that are easy to invert, see Alon, Babai, Itai (1986), Luby (1986), Schnorr (1988), Maurer, Massey (1989), Naor, Naor (1990), Nisan (1990) and Alon, Goldreich, Hastad, Peralta (1990). Most of these constructions are methodically simple and are not directed towards cryptographic applications. They aim at minimizing the number of random bits that are used in randomised algorithms. Merely the quadratic character construction by Alon et alii (1990) is similar to our generator, it relies on Weil’s theorem. Our proof of local randomness relies on upper bounds for exponential sums and an inequality on quantitative Fourier inversion. We use upper bounds for the discrepancy of polynomial residues from Niederreiter (1977) and we extend these bounds from prime moduli to arbitrary squarefree moduli.

We also establish random function generators, associated with fixed polynomials, that provide local randomness. These generators are candidates for cryptographic hash functions. We associate with a polynomial P ∈ ZZ_{N}[x] of degree d a polynomial function family P_{z}(y) = P (z + y) where z is the function name and y is the input. For fixed k, m ≤ log_{2} N we associate with a random z ∈ ZZ_{N} a random function

P_{z}^{m} : [0, 2^{k} − 1] ⟶ {0, 1}^{m} , y ⟼ P (z + y) [m

where P (z + y)[m denotes the bit string consisting of the m least significant bits of the residue P (z + y) mod N in [0, N − 1].

We call a function family {P_{z}} (ε, e)–locally random if for random z and for any e distinct points y_{1}, …, y_{e} the distribution of the em–bit string P_{z}(y_{1}) ⋯ P_{z}(y_{e}) is in the L_{1}–norm at most ε away from the uniform distribution on em–bit strings.

We prove in Theorem 6 that the above family of functions {P_{z}^{m}} is (ε, e)– locally random, if N is prime, d = deg P satisfies e + 1 ≤ d < N and if

N^{−1/2}(log N)^{e+1}2^{em+2}d ≤ ε.

A family of functions is an e–universal family of hash functions as introduced by Carter and Wegman (1979) if and only if it is (0, e)–locally random. Our hash functions require fewer random bits than those of Carter and Wegman since we only randomize the input of the polynomial whereas Carter and Wegman randomize all its coefficients. The main point however is that our hash–functions are – if deg P is sufficiently large – candidates for cryptographically secure hashing whereas the Carter–Wegman hash functions are easy to invert. Thus for the first time we establish local randomness in families of cryptographic hash functions.

2 Random Number Generators that Provide Statistical Local Randomness

We present in Theorem 1 our main result and we derive from it RNG’s that are locally random. In order to prove Theorem 1 we establish in Theorem 3 an upper bound on the discrepancy for multidimensional polynomial number sequences. This upper bound relies on an upper bound for exponential sums given in Lemma 4 and on an inequality of Niederreiter (1977) on quantitative Fourier inversion.

Notation. Let p_{1}, …, p_{r} be r distinct primes, N = p_{1} ⋯ p_{r} (i.e. N is squarefree) and ZZ_{N} = ZZ/NZZ. Let F = (f_{1}, …, f_{ℓ}) be an ℓ–tuple of polynomials f_{j} ∈ ZZ[x], j = 1, …, ℓ. We denote by d_{i}(f_{j}) the degree of f_{j} when f_{j} is considered mod p_{i} and we put d_{i}(F) = max_{1≤j≤ℓ} d_{i}(f_{j}). We define c_{i}(F) = min(d_{i}(F) − 1, \sqrt{p_{i}}) for i = 1, …, r and c(F) = ∏_{i=1}^{r}(c_{i}(F) + 1) . We call F N–admissible if for every prime divisor p_{i} of N the polynomials f_{1}, …, f_{ℓ} are linearly independent modulo the subspace of polynomials of degree ≤ 1 in ZZ_{p_{i}}[x]. In this case we also call the set of polynomials f_{1}, …, f_{ℓ} N–admissible. Thus f_{1}, …, f_{ℓ} are N–admissible if for i = 1, …, r and for all a_{1}, …, a_{ℓ} ∈ ZZ either the polynomial ∑_{j=1}^{ℓ} a_{j}f_{j}(mod p_{i}) is non–linear or a_{1} = ⋯ = a_{ℓ} = 0(mod p_{i}).

We let log N denote the natural logarithm of N. We identify ZZ_{N} with the integer interval [0, N −1]. We abbreviate the set {0, 1}^{n} as I_{n} and we identify the integer interval [0, 2^{n} −1] with I_{n} . If y ∈ [0, N −1] = ZZ_{N} and n ≤ log_{2} N we let y[n ∈ I_{n} denote the bit string consisting of the n least significant bits of y. Let IN denote the set of positive integers.

A collection of m least significant output bits. We associate with F = (f_{1}, …, f_{ℓ}) ∈ (ZZ[x])^{ℓ} , N ∈ IN and m = (m_{1}, …, m_{ℓ}) ∈ IN^{ℓ} the mapping

Fm : [0, N − 1] → I_{m} , x ↦ ∏_{j=1}^{ℓ}(f_{j}(x)[m_{j}) with f_{j}(x) ∈ ZZ_{N},

where m = ∑_{j=1}^{ℓ} m_{j} and ∏ is the concatenation of strings. The mapping Fm outputs a collection of m least significant bits of F(x), where F(x) is taken modulo N.

Our main theorem provides explicit estimates for the max–norm difference between the distribution induced by Fm(x) for random x ∈ [0, M −1] ⊂ [0, N −1], N–admissible F and the uniform distribution on {0, 1}^{m}.

Theorem 1. Let N be odd and squarefree, let F, m, m, Fm be as above and let F be N–admissible. Then for N > 148, 1 ≤ M ≤ N and random x ∈ [0, M − 1] we have that

max_{z∈\{0,1\}^{m}} |prob[Fm(x) = z] − 2^{−m}| ≤ \frac{4}{M} \sqrt{N}(log N)^{l+1}c(F) .

The condition that F is N–admissible cannot be completely removed from Theorem 1. Theorem 1 does not hold for linear polynomials f_{1}, …, f_{ℓ} with ℓ ≥ 2. This is because the least significant bits in two linear polynomials are highly correlated. On the other hand our proof shows that Theorem 1 holds for a single polynomial of degree 1 in the case that N = M.

For example let N > 2^{512} be prime and let d = 2^{32}. Then the polynomials x^{2}, …, x^{d} are N–admissible. Consider for random x ∈ [0, N − 1] the bit string (x^{2}[1, …, x^{d}[1) ∈ I_{d−1}. For any choice of 24 bit positions 2 ≤ i_{1} < i_{2} ⋯ < i_{24} ≤ 2^{32} and every z ∈ {0, 1}^{24} we have that

|prob(x^{i_{1}}[1 ⋯ x^{i_{24}}[1 = z) − 2^{−24}| < 2^{−44} .

This follows from Theorem 1 with ℓ = 24, f_{j} = x^{i_{j}} for j = 1, …, 24, N = M and c(F) ≤ 2^{32}.

Definition. A random variable y ranging over a finite set S is called statistically random within ε (in S) if ∑_{s∈S} |prob(y = s) − 1/#S| ≤ ε , i.e. the L_{1}–norm statistical difference of y from the uniform distribution on S is at most ε.

Definition. A probability distribution D on I_{n} is called (ε, e)–locally random if for any sequence of positions 1 ≤ j_{1} < j_{2} < ⋯ < j_{e} ≤ n the substring (y_{j_{1}}, …, y_{j_{e}}) ∈ I_{e} of a D–random string y = (y_{1}, …, y_{n}) is statistically random within ε.

Using Theorem 1 we can stretch a short random seed into a long bit string that is “locally random”.

Corollary 2. Let N = p_{1} ⋯ p_{r} be a product of r distinct odd primes, 1 ≤ M ≤ N and N > 148 . Let f_{1}, …, f_{ℓ} ∈ ZZ[x] be polynomials of degree at most d that are N–admissible. Then for random x ∈ [0, M − 1] the bit string (f_{1}(x)[1, …, f_{ℓ}(x)[1) ∈ I_{ℓ} with f_{j}(x) ∈ ZZ_{N} is (ε, e)–locally random with ε = 2\frac{\sqrt{N}}{M} (2 log N)^{e+1}d^{r} for e = 1, …, ℓ.

Proof. Let 1 ≤ j_{1} < j_{2} < ⋯ < j_{e} ≤ ℓ be any sequence of e output bit positions. We apply Theorem 1 with F = (f_{j_{1}}, …, f_{j_{e}}), m = (1, …, 1) ∈ IN^{e} and m = ℓ = e. The L_{1}–norm difference between the distribution induced by Fm(x) ∈ {0, 1}^{e} and the uniform distribution is at most 2^{e}–times the max–norm difference. We have c(F) ≤ d^{r}, and thus by Theorem 1 F(x) is statistically random within 2\frac{\sqrt{N}}{M} (2 log N)^{e+1}d^{r}. □

The discrepancy D_{M}^{(ℓ)} = D_{M}^{(ℓ)}(y_{1}, …, y_{M}) of M points y_{1}, …, y_{M} ∈ [0, 1)^{ℓ} is defined to be

D_{M}^{(ℓ)}(y_{1}, …, y_{M}) = sup_{I} |F_{M}(I) − V (I)|

where I ranges over all half–open subintervals I of [0, 1)^{ℓ} , i.e.

I = {(z_{1}, …, z_{ℓ}) ∈ [0, 1)^{ℓ} | a_{i} ≤ z_{i} < b_{i} for i = 1, …, ℓ}

with 0 ≤ a_{i} < b_{i} ≤ 1 for i = 1, …, ℓ. V (I) is the volume of I and F_{M}(I) = M^{−1}#{k | y_{k} ∈ I} .

The proof of Theorem 1 relies on the following upper bound for the discrepancy of multidimensional polynomial sequences. For a real number a we let {a} denote the residue of a mod ZZ in the real interval [0, 1).

Theorem 3. Let N be squarefree and let D_{M}^{(ℓ)} be the discrepancy of the M points (\{\frac{f_{1}(k)}{N}\} , …, \{\frac{f_{ℓ}(k)}{N}\}) ∈ [0, 1)^{ℓ} for k = 1, …, M. If F = (f_{1}, …, f_{ℓ})

is N–admissible then D_{M}^{(ℓ)} ≤ \frac{4B}{M} \sqrt{N} (log N)^{ℓ+1}c(F) for 1 ≤ M ≤ N and N > 148. Here B = \sqrt{2} if N is even and B = 1 if N is odd.

The proof is based on a bound for exponential sums. For f ∈ ZZ[x] and n ∈ IN define

S(f, n) = ∑_{x=1}^{n} e (\frac{f(x)}{n}) with e(u) = e^{2π\sqrt{−1}u} for u ∈ IR.

The proofs for Lemmata 4 and 5 are omitted due to lack of space. They are contained in the complete paper that is to appear in Siam J. Computing.

Lemma 4. If N = p_{1} … p_{r} is squarefree, B is as in Theorem 3, and f ∈ ZZ[x] is arbitrary, then |S(f, N)| ≤ B\sqrt{N} ∏_{i=1}^{r} c′_{i}(f), where c′_{i}(f) = \sqrt{p_{i}} if d_{i}(f) < 1 and c′_{i}(f) = min(d_{i}(f) − 1, \sqrt{p_{i}}) if d_{i}(f) ≥ 1.

Lemma 5. Let D_{M}^{(ℓ)} be the discrepancy of the M points y_{k} ∈ [0, 1)^{ℓ} for k = 1, …, M and let D_{N}^{(ℓ+1)} be the discrepancy of the N points (y_{k}, \frac{k−1}{N}) for k = 1, …, N. Then D_{M}^{(ℓ)} ≤ \frac{N}{M} D_{N}^{(ℓ+1)} for 1 ≤ M ≤ N .

Proof of Theorem 3. Let N have r distinct prime factors. Put C_{ℓ}(N) = (−N/2, N/2]^{ℓ} ∩ ZZ^{ℓ}, C_{ℓ}^{∗}(N) = C_{ℓ}(N)\{0} (here we use, as in Niederreiter (1977), the interval (−N/2, N/2] rather than [0, N)) . For h = (h_{1}, …, h_{ℓ}) ∈ C_{ℓ}(N) we put

r(h, N) = ∏_{j=1}^{ℓ} r(h_{j}, N) with r(h_{j}, N) = \{ \begin{matrix}1 & if h_{j} = 0 \\ N sin \frac{π|h_{j}|}{N} & if h_{j} ≠ 0. \end{matrix}

By Lemma 2.2 of Niederreiter (1977), we get

D_{N}^{(ℓ+1)} ≤ \frac{ℓ + 1}{N} + \frac{1}{N} ∑_{h∈C_{ℓ+1}^{∗}(N)} \frac{1}{r(h, N)} |S(h_{1}f_{1} + … + h_{ℓ}f_{ℓ} + h_{ℓ+1}x, N)|, (3)

where h = (h_{1}, …, h_{ℓ+1}) and f_{1}, …, f_{ℓ} ∈ ZZ[x]. By Lemma 4

|S(h_{1}f_{1} + … + h_{ℓ}f_{ℓ} + h_{ℓ+1}x, N)| ≤ BN^{1/2} ∏_{i=1}^{r} c′_{i}(h_{1}f_{1} + … + h_{ℓ}f_{ℓ} + h_{ℓ+1}x). (4)

If h ∈ C_{ℓ+1}^{∗}(N) with (h_{1}, …, h_{ℓ}) = 0, then c′_{i}(h_{1}f_{1} + … + h_{ℓ}f_{ℓ} + h_{ℓ+1}x) = c′_{i}(h_{ℓ+1}x) = 0 for some i, namely when h_{ℓ+1} ≠ 0 mod p_{i}, and so

∏_{i=1}^{r} c′_{i}(h_{1}f_{1} + … + h_{ℓ}f_{ℓ} + h_{ℓ+1}x) = 0.

Thus we only have to consider those h ∈ C_{ℓ+1}^{∗}(N) with (h_{1}, …, h_{ℓ}) ≠ 0. We split up the set of (h_{1}, …, h_{ℓ}) ∈ C_{ℓ}^{∗}(N) according to the set of i’s for which d_{i}(h_{1}f_{1} + … + h_{ℓ}f_{ℓ}) ≤ 1. For I ⊆ A_{r} := {1, 2, …, r} we put H(I) = {(h_{1}, …, h_{ℓ}) ∈ C_{ℓ}^{∗}(N) : d_{i}(h_{1}f_{1} + … + h_{ℓ}f_{ℓ}) ≤ 1 if and only if i ∈ I}. If (h_{1}, …, h_{ℓ}) ∈ H(I) and i ∈ A_{r}\I, then for any h_{ℓ+1} ∈ C_{1}(N) we have

d_{i}(h_{1}f_{1} + … + h_{ℓ}f_{ℓ} + h_{ℓ+1}x) = d_{i}(h_{1}f_{1} + … + h_{ℓ}f_{ℓ}) ≥ 2.

Since d_{i}(h_{1}f_{1} + … + h_{ℓ}f_{ℓ}) ≤ d_{i}(F), it follows that

c′_{i}(h_{1}f_{1} + … + h_{ℓ}f_{ℓ} + h_{ℓ+1}x) ≤ c_{i}(F).

Using the trivial bound c′_{i}(f) ≤ p_{i}^{1/2}, we obtain

∏_{i=1}^{r} c′_{i}(h_{1}f_{1} + … + h_{ℓ}f_{ℓ} + h_{ℓ+1}x) ≤ ∏_{i∈I} p_{i}^{1/2} · ∏_{i∈A_{r}\I} c_{i}(F)

for any (h_{1}, …, h_{ℓ}) ∈ H(I) and h_{ℓ+1} ∈ C_{1}(N). Together with (3) and (4) this yields

D_{N}^{(ℓ+1)} ≤ \frac{ℓ + 1}{N}
+ BN^{−1/2} ∑_{I⊆A_{r}} ∏_{i∈I} p_{i}^{1/2} · ∏_{i∈A_{r}\I} c_{i}(F) ∑_{h∈H(I)} \frac{1}{r(h, N)} ∑_{h_{ℓ+1}∈C_{1}(N)} \frac{1}{r(h_{ℓ+1}, N)}.

Using the inequality

∑_{h∈C_{1}^{∗}(m)} \frac{1}{r(h, m)} < \frac{2}{π} log m + \frac{2}{5} for m ≥ 2 (5)

from Niederreiter [14, (2.7)] this yields

D_{N}^{(ℓ+1)} < \frac{ℓ + 1}{N}
+ BN^{−1/2} (\frac{2}{π} log N + \frac{7}{5}) ∑_{I⊆A_{r}} ∏_{i∈I} p_{i}^{1/2} · ∏_{i∈A_{r}\I} c_{i}(F) ∑_{h∈H(I)} \frac{1}{r(h, N)}.

By the assumption of the theorem (f_{1}, …, f_{ℓ}) is N–admissible. Therefore if (h_{1}, …, h_{ℓ}) ∈ H(I) we get h_{k} = 0 mod p_{i} for i ∈ I and 1 ≤ k ≤ ℓ, thus h_{k} = 0 mod ∏_{i∈I} p_{i} for 1 ≤ k ≤ ℓ. Therefore with L = ∏_{i∈I} p_{i} we obtain

∑_{h∈H(I)} \frac{1}{r(h, N)} ≤ ∑ ; h=0modL^{h∈C{∗ \atop ℓ}(N)} \frac{1}{r(h, N)} = ∑_{h∈C_{ℓ}(N/L)} \frac{1}{r(Lh, N)} − 1

= ( ∑_{h∈C_{1}(N/L)} \frac{1}{r(Lh, N)})^{ℓ} − 1

= (1 + ∑_{h∈C_{1}^{∗}(N/L)} \frac{1}{r(Lh, N)})^{ℓ} − 1

= (1 + \frac{1}{L} ∑_{h∈C_{1}^{∗}(N/L)} \frac{1}{r(h, N/L)})^{ℓ} − 1

< (1 + \frac{1}{L} (\frac{2}{π} log \frac{N}{L} + \frac{2}{5}))^{ℓ} − 1  (by the inequality (5))

< \frac{ℓ}{L} (\frac{2}{π} log N + \frac{7}{5})^{ℓ} ,

where we applied the mean–value theorem in the last step. It follows that

D_{N}^{(ℓ+1)} < \frac{ℓ + 1}{N} + BℓN^{−1/2} (\frac{2}{π} log N + \frac{7}{5})^{ℓ+1} ∑_{I⊆A_{r}} ∏_{i∈I} p_{i}^{−1/2} · ∏_{i∈A_{r}\I} c_{i}(F)

= \frac{ℓ + 1}{N} + BℓN^{−1/2} (\frac{2}{π} log N + \frac{7}{5})^{ℓ+1} ∏_{i=1}^{r}(c_{i}(F) + p_{i}^{−1/2})

< BN^{−1/2}(log N)^{ℓ+1}c(F) (\frac{ℓ + 1}{N^{1/2}(log N)^{ℓ+1}} + ℓ (\frac{2}{π} + \frac{7}{5 log N} )^{ℓ+1})

< BN^{−1/2}(log N)^{ℓ+1}c(F) (\frac{1}{60}(ℓ + 1)5^{−ℓ} + ℓ(\frac{2}{π} + \frac{7}{25})^{ℓ+1})

< 4BN^{−1/2}(log N)^{ℓ+1}c(F)

provided that log N ≥ 5, i.e. that N > 148 . Together with Lemma 5 we get the result of Theorem 3. □

Proof of Theorem 1 Let N be an odd squarefree integer and \overline{f}_{j} ∈ ZZ[x] be polynomials such that \overline{f}_{j}(x) = 2^{−m_{j}}f_{j}(x)(modN) for j = 1, …, ℓ. Applica-

tion of Theorem 3 to \overline{F} = (\overline{f}_{1}, …, \overline{f}_{ℓ}) shows that the discrepancy \overline{D}_{M}^{(ℓ)} of ({f̄_{1}(k)/N}, …, {f̄_{ℓ}(k)/N}) for k = 1, …, M satisfies

\overline{D}_{M}^{(ℓ)} ≤ \frac{4}{M} \sqrt{N}(log N)^{ℓ+1}c(F),

where we use that c(F) = c(\overline{F}). We apply to this inequality the equivalence

\{\overline{f}_{j}(x)/N\} ∈ [k_{j}2^{−m_{j}}, (k_{j} + 1)2^{−m_{j}}) ⟺
[f_{j}(x)]_{N} = −k_{j}N(mod2^{m_{j}}) for j = 1, …, ℓ ,

where [f_{j}(x)]_{N} is the residue of f_{j}(x) mod N in [0, N −1], and 0 ≤ k_{j} < 2^{m_{j}}. To see the equivalence we note that \{\overline{f}_{j}(x)/N\} ∈ [k_{j}2^{−m_{j}}, (k_{j} +1)2^{−m_{j}}) implies that there is an integer y satisfying

k_{j}N ≤ y < (k_{j} + 1)N, y = f_{j}(x) mod N, y = 0 mod 2^{m_{j}} ,

and thus [f_{j}(x)]_{N} = −k_{j}N(mod2^{m_{j}}). This proves one direction of the equivalence and the converse direction is an immediate consequence.

We see from the above inequality and the equivalence that for every y ∈ {0, 1}^{m}

|\frac{1}{M} #\{x ∈ [1, M] : Fm(x) = y\} − \frac{1}{2^{m}} | ≤ \frac{4}{M} \sqrt{N}(log N)^{ℓ+1}c(F).

□

The above proof of Theorem 1 extends to the following larger class of functions Fu. Let the polynomials f_{1}, …, f_{ℓ} ∈ ZZ_{N}[x] be N–admissible and let u_{1}, …, u_{ℓ} be integers that are relatively prime to N, F = (f_{1}, …, f_{ℓ}) and u = (u_{1}, …, u_{ℓ}). Define Fu as

Fu : [0, N − 1] ∋ x ↦ ( (f_{i}(x) mod N) mod u_{i} | for i = 1, …, ℓ).

Corollary 6. For N > 148, 1 ≤ M ≤ N and random x ∈ [0, M −1] the max– norm difference between the distribution induced by Fu(x) and the uniform distribution on [0, u_{1} − 1] × ⋯ × [0, u_{ℓ} − 1] is at most \frac{4}{M} \sqrt{N}(log N)^{ℓ+1}c(F).

Theorem 1 deals with the particular case that the integers u_{i} are powers of 2. It is necessary that u_{1}, …, u_{ℓ} are relatively prime to N. The proof of the Corollary uses the polynomials f̄_{j} = u_{j}^{−1}f_{j}(modN) and thus requires a division by u_{j} modulo N.

3 Random Function Generators that Provide Statistical Local Randomness

Let H_{k,ℓ} = I_{ℓ}^{I_{k}} = “the set of functions f : I_{k} → I_{ℓ}”. A random function generator F is an efficient algorithm that generates from names x ∈ I_{n} a function f_{x} = F (x, ∗) ∈ H_{k,ℓ}.

We call a probability distribution D on H_{k,ℓ} (ε, e)–locally random if for random f, f ∈_{D} H_{k,ℓ}, for any set of e distinct inputs y_{1}, …, y_{e} ∈ I_{k} the concatenated output f(y_{1})f(y_{2}) ⋯ f(y_{e}) ∈ I_{eℓ} is statistically random within ε.

The concept of (ε, e)–locally random distribution D on H_{k,ℓ} extends the concept of universal hash functions of Carter and Wegman (1979). If D is (0, e)– locally random then for any distinct inputs y_{1}, …, y_{e} ∈ I_{k} the bit string f(y_{1})f(y_{2}) ⋯ f(y_{e}) ∈ I_{e} is truly random, i.e. D is the probability distribution of an e–universal family of hash functions in the sense of Carter and Wegman.

Carter and Wegman show how to generate an e–universal family of hash functions in H_{k,k} from ke random bits. Let K = GF (2^{k}) be the field with 2^{k} elements. If (a_{0}, …, a_{e−1}) ∈ K^{e} is random then the polynomial P = ∑_{i=0}^{e−1} a_{i}x^{i} ∈ K[x] yields an e–universal family of hash functions in H_{k,k}.

Let N be a prime and P ∈ ZZ_{N}[x] be a polynomial with coefficients in the field ZZ_{N}. We associate with P and k, ℓ ∈ IN , k, ℓ ≤ log_{2} N, the function

P^{ℓ} : ZZ_{N} × [0, 2^{k} − 1] → I_{ℓ} , (z, y) ↦ P (y + z)[ℓ.

Here we let P (y + z)[ℓ , for ℓ ≤ log_{2} N , denote the bit string consisting of the ℓ least significant bits of the residue of P (y + z) mod N that is in ZZ_{N}. We let P_{z}^{ℓ} : I_{k} → I_{ℓ} denote the function P^{ℓ}(z, ∗).

Theorem 7. Let N be prime, N > 148 , P ∈ ZZ_{N}[x] , k, ℓ ≤ log_{2} N, let P_{z}^{ℓ} : I_{k} → I_{ℓ} be as above and let e + 1 ≤ deg P < N. Then for random z ∈ ZZ_{N} the family of functions {P_{z}^{ℓ}} is (ε, e)–locally random with ε = N^{−1/2}(log N)^{e+1}2^{eℓ+2} deg P.

Proof. Let d = deg P, let y_{1}, …, y_{e} ∈ ZZ_{N} be pairwise distinct and let f_{i} ∈ ZZ_{N}[x] be the polynomial f_{i}(x) = P (y_{i} + x) for i = 1, …, e. We next show that the polynomials f_{1}, …, f_{e} are linearly independent modulo the subspace of polynomials of degree ≤ 1 in ZZ_{N}[x]. For suppose that there are b_{1}, …, b_{e} ∈ ZZ_{N} such that

deg (∑_{i=1}^{e} b_{i}P (y_{i} + x)) ≤ 1.

Then for j = d − e + 1, …, d the j–th derivative of this linear combination vanishes at x = 0 , hence

∑_{i=1}^{e} b_{i}P^{(j)}(y_{i}) = 0 for j = d − e + 1, …, d.

It is sufficient to prove that the coefficient matrix [P^{(j)}(y_{i})]_{{1≤i≤e \atop d−e+1≤j≤d}} is nonsingular since this implies that b_{1} = ⋯ = b_{e} = 0. Suppose that there exist h_{d−e+1}, …, h_{d} ∈ ZZ_{N} such that

∑_{j=d−e+1}^{d} h_{j}P^{(j)}(y_{i}) = 0 for 1 ≤ i ≤ e.

Put g(x) = ∑_{j=d−e+1}^{d} h_{j}P^{(j)}(x), then g(y_{i}) = 0 for 1 ≤ i ≤ e . Since y_{1}, …, y_{e} are distinct and deg(g) ≤ d − (d − e + 1) = e − 1 we have g = 0, so

∑_{j=d−e+1}^{d} h_{j}P^{(j)}(x) = 0.

Comparing coefficients of x^{e−1} we get h_{d−e+1} = 0 (the coefficient of x^{e−1} in P^{(d−e+1)} is nonzero since d < N). Continuing in this manner, we obtain h_{d−e+1} = ⋯ = h_{d} = 0 . Since f_{1}, …, f_{e} are linearly independent modulo ZZ_{N} + xZZ_{N} we can apply Theorem 1 to F = (f_{1}, …, f_{e}). Since ∏_{j=1}^{e} f_{j}(z)[ℓ ∈ I_{eℓ} the m in Theorem 1 is eℓ. The ℓ in Theorem 1 is e. Hence ∏_{j=1}^{e} P (y_{j} + z)[ℓ ∈ I_{eℓ} is statistically random within ε = N^{−1/2}(log N)^{e+1}d 2^{eℓ+2}. Therefore {P_{z}^{ℓ}} is (ε, e)–locally random. □

References

[1] Alexi, W., Chor, B., Goldreich, O. and Schnorr, C.P.: RSA and Rabin Functions: certain parts are as hard as the whole. SIAM J. Comput., 17, 2 (1988), pp. 194 – 208.

[2] Alon, N., Babai, L. and Itai, A.: A fast and simple randomised parallel algorithm for the maximal independent set problem. J. of Alg. 7 (1986), pp. 567 – 583.

[3] Alon, N., Goldreich, O., Hastad, J. and Peralta, R.: Simple constructions of almost k–wise independent random variables. Proceedings of the 31st IEEE Symposium on Foundations of Computer Science (1990) pp. 544 – 552.

[4] Blum, L, Blum, M., and Shub, M.: A simple unpredictable pseudo–random number generator. SIAM J. Comput. 15 (1986), pp. 364 – 383.

[5] Blum, M. and Micali, S.: How to generate cryptographically strong sequences of pseudo–random bits. Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, IEEE, New York (1982); also SIAM J. Comput. 13 (1984), pp. 850–864.

[6] Carlitz, L. and Uchiyama, S.: Bounds for exponential sums. Duke Math. J. 24, (1957), pp. 37 – 41.

[7] Carter, L. and Wegman, M.: Universal hash functions. J. Comp. and Syst. Sci. 18, (1979) pp. 143 – 154.

[8] Goldreich, O., Goldwasser, S. and Micali, S.: How to Construct Random Functions. Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, New York, (1984); also Journal ACM 33, 4 (1986), pp. 792–807.

[9] Lidl, R., and Niederreiter, H.: Finite Fields. Reading: Addison–Wesley 1983.

[10] Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15 (1986), pp. 1036 – 1053.

[11] Maurer, U. M., and Massey, J.L.: Perfect local randomness in pseudo–random sequences. Proceedings Crypto ’89, Lecture Notes in Computer Science, Vol. 435, Springer–Verlag 1990, pp. 100–112.

[12] Micali, S. and Schnorr, C.P.: Efficient, perfect polynomial random number generators. J. of Cryptology 3, (1991), pp. 157 – 172.

[13] Naor, J. and Naor, M.: Small–bias Probability Spaces: Efficient Constructions and Applications. Proceedings of the 22nd ACM Symposium on Theory of Computing (1990), pp. 213–223.

[14] Niederreiter, H.: Pseudo–random numbers and optimal coefficients. Advances in Math. 26, (1977) pp. 99 – 181.

[15] Nisan, N.: Pseudorandom generators for space–bounded computation. Proceedings of the 22nd ACM Symposium on Theory of Computing (1990), pp. 204–208.

[16] Schnorr, C.P.: On the construction of random number generators and random function generators. Proc. EUROCRYPT ’88, Lecture Notes in Computer Science, Vol. 330, Springer–Verlag 1988, pp. 225–232.

[17] Weil, A.: On some exponential sums. Proc. Nat. Acad. Sci. USA 34, (1948), pp. 204 – 207.

[18] Yao, A.C.: Theory and applications of trapdoor functions. Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, IEEE, New York (1982), pp. 80–91.

This article was processed using the LaTEX macro package with LLNCS style