On the security of modular exponentiation with application to the construction of pseudorandom generators (Q1402365)

Let \(N_n\) be the set of all \(n\)-bit integers \(P\cdot Q\), where \(P\) and \(Q\) are two odd primes of equal length. Let \(P_n\) be the set or pairs \(\langle N,g\rangle\) with \(N\in N_n\) and \(g\in \mathbb{Z}^*_N\), the multiplicative group of naturals \(\leq N\) and coprime to \(N\). Let \(\langle N,g\rangle\) be a uniformly distributed (u.d.) pair in \(P_n\), \(R\) u.d. in \([0,\text{ord}_N(g))\) and \(r\) u.d. in \(\{0,1\}^{\lceil n/2\rceil}\). Then \(\text{Full}_n\) denotes the distribution \(\langle N,g,g^R \bmod N\rangle\) and \(\text{Half}_n\) the distribution \(\langle N,g,g^r \bmod N\rangle\). Assuming the intractability of factoring, the authors prove that the ensembles \(\{\text{Half}_n\}_{n\in\mathbb N}\) and \(\{\text{Full}_n\}_{n\in\mathbb N}\) are computationally indistinguishable. They also show that this result is equivalent to the result by \textit{J. Håstad}, \textit{A. W. Schrift} and \textit{A. Sharmir} [J. Comput. Syst. Sci. 47, 376--404 (1993; Zbl 0790.94013)] on the simultaneous hardness of the upper \(\lceil n/2\rceil\) bits in the exponentiation function \(f_{N,g}(x)=g^x\bmod N\) (the interested reader should also consult the footnote on p.~87). Application towards an efficient factoring-based pseudorandom generator which nearly doubles the length of its input is given. To this aim a general method on how to pick a random \(n\)-bit prime using only a linear number of random bits is also described.