Pseudorandom numbers and hash functions from iterations of multivariate polynomials (Q2380848)

The authors study the distribution of pseudorandom vectors derived from triangular polynomial systems introduced by the authors in [Math. Comput. 79, 501--511 (2010; Zbl 1227.11093)], further analysed by the first author in [``Multivariate permutation polynomial systems and nonlinear pseudorandom number generators'', Finite Fields Appl. 16, 144--154 (2010; Zbl 1192.11047)], and defined as follows. Let \(F_0,\dots,F_{m}\in \mathbb F_p[X_0,\dots,X_m]\) be \(m+1\) polynomials of the form \[ \begin{aligned} F_0(X_0,\dots,X_m)&= X_0G_0(X_1,\dots,X_m)+H_0(X_1,\dots,X_m),\\ F_1(X_0,\dots,X_m)&= X_1G_1(X_2,\dots,X_m)+H_1(X_2,\dots,X_m),\\ &\dots\\ F_{m-1}(X_0,\dots,X_m)&= X_{m-1}G_{m-1}(X_m)+H_{m-1}(X_m),\\ F_{m}(X_0,\dots,X_m)&= X_{m}g_{m}+h_{m}, \end{aligned} \] where \(g_m,h_m\in \mathbb F_p\), \(g_m\neq 0\), \(G_i,H_i\in \mathbb F_p[X_{i+1},\dots,X_m]\), \(i=0,\dots,m-1\). They define a sequence of \((m+1)\)-dimensional vectors \[ (u_{n,0},\dots,u_{n,m})\in \mathbb F_p^{m+1} \] by \[ u_{n+1,i}=F_i(u_{n,0},\dots,u_{n,m}),\quad n\geq 0, \] with some initial vector \((u_{0,0},\dots,u_{0,m})\) and study exponential sums of the form \[ \sum_{n=0}^{N-1} \exp\left(2\pi i\sum_{i=0}^j a_i u_{n,i}/p\right), \] where \(j=m\) or \(j=m-1\). For \(j=m\) they improve earlier results. The case \(j=m\) couldn't be treated before. The new idea is to use a result of \textit{J. Bourgain, A. A. Glibichuk}, and \textit{S. V. Konyagin} [J. Lond. Math. Soc., II. Ser. 73, No. 2, 380--398 (2006; Zbl 1093.11057)]. The exponential sum bounds need restrictions on the relative degrees of the \(G_i\) and \(H_i\) where the first author studied another case that the \(G_i\) are constant in [Arithmetic of finite fields. Third international workshop, WAIFI 2010, Istanbul, Turkey, 2010. Proceedings. Berlin: Springer, Lect. Notes Comput. Sci. 6087, 62--72 (2010; Zbl 1231.11090)]. As an application the authors design a new class of hash functions. In the univariate case results of this strength are not possible because of the exponential degree growth of iterated polynomials, see \textit{H. Niederreiter} and the second author [ Finite Fields Appl. 5, No. 3, 246--253 (1999; Zbl 0942.11037)], \textit{A. Topuzŏglu} and the reviewer [``Pseudorandom sequences'', Topics in geometry, coding theory and cryptography. Dordrecht: Springer. Algebra and Applications 6, 135--166 (2007; Zbl 1134.11030)], or \textit{H. Niederreiter} and the reviewer [Finite Fields Appl. 14, No. 1, 59--64 (2008; Zbl 1231.11096)]. Additionally, bounds on the linear complexity of the vector sequence studied in this paper are given by the authors and the reviewer in [Adv. Math. Commun. 4, No. 3, 369--379 (2010; Zbl 1215.65009)].