On the security of modular exponentiation with application to the construction of pseudorandom generators
type: Item
instance of: scholarly article
title: On the security of modular exponentiation with application to the construction of pseudorandom generators
zbMATH Open document ID: 1040.94006
author: Oded Goldreich
author: Vered Rosen
published in: Journal of Cryptology
publication date: 2003-08-27T00:00:00Z
review text: 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.
reviewed by: Štefan Porubský
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 1971853
zbMATH Keywords: modular exponentiation
zbMATH Keywords: discrete logarithm
zbMATH Keywords: hard-core predicate
zbMATH Keywords: simultaneous security
zbMATH Keywords: pseudorandom generator
zbMATH Keywords: factoring assumption
MaRDI profile type: Publication
full work available at URL: s00145-002-0038-7
OpenAlex ID: W1979828147
DOI: 10.1007/S00145-002-0038-7
Recommended article: Pseudo-random functions and factoring (extended abstract)
Recommended article: Q4536819
Recommended article: An improved pseudo-random generator based on the discrete logarithm problem
Recommended article: Q4249340
Recommended article: Q3702366
Recommended article: The discrete logarithm modulo a composite hides \(O(n)\) bits
Recommended article: RSA and Rabin Functions: Certain Parts are as Hard as the Whole
Recommended article: Factoring polynomials using fewer random bits
Recommended article: Q4414270
Recommended article: Pseudorandom Functions and Factoring
description: scientific article; zbMATH DE number 1971853