On the uniformity of distribution of the Naor-Reingold pseudo-random function (Q5941622)

Let \(p\) be an \(n\)-bit prime, \(t\) be a prime divisor of \(p-1\), and \(g\in \mathbb{F}_p^*\) be an element of multiplicative order \(t\). For each \(n\)-dimensional vector \({\mathbf a}=(a_1,\ldots,a_n)\in (\mathbb{Z}/t)^n\) the function \(f_{\mathbf a}(x)\) is defined by \[ f_{\mathbf a}(x)=g^{a_1^{x_1}\cdots a_n^{x_n}}, \] where \(x=x_1\ldots x_n\) is the bit representation of an integer \(0\leq x\leq 2^n-1\). \textit{M. Naor} and \textit{O. Reingold} [Number theoretic constructions of efficient pseudo-random functions, in Proc. 38th IEEE Symp. Found. Comput. Sci., 458--467 (1997)] proposed this function as an efficient pseudo-random function. In the paper under review the author shows that the sequence \(f_{\mathbf a}(x)\), \(x=0,1,\ldots,2^n-1\), is asymptotically uniformly distributed. The result is based on the bounds of character sums with exponential sums obtained by \textit{S. V. Konyagin} and the author [Character sums with exponential functions and their applications, Cambridge Univ. Press, Cambridge (1999; Zbl 0933.11001)]. Lower bounds on the linear and nonlinear complexity of this generator have been obtained in \textit{F. Griffin} and the author [Lect. Notes Comput. Sci. 1726, 301--308 (1999; Zbl 0982.94013)], the author [Linear complexity of the Naor-Reingold pseudo-random function, Inform. Process. Lett. 76, 95--99 (2000)], and \textit{W. Banks, F. Griffin, D. Lieman}, and the author [Nonlinear complexity of the Naor-Reingold pseudo-random function, Lect. Notes Comput. Sci. 1787, 53--59 (2000; Zbl 1032.94507)]. For the elliptic curve version of the Naor-Reingold generator see the author [Appl. Algebra Eng. Commun. Comput. 11, No. 1, 27--34 (2000; Zbl 1011.11055)] and the author and \textit{J. H. Silverman} [Des. Codes Cryptography 24, 279-2-89 (2001; Zbl 1077.11504)].