Alexi, Werner; Chor, Benny; Goldreich, Oded; Schnorr, Claus P. RSA and Rabin functions: Certain parts are as hard as the whole. (English) Zbl 0644.94011 SIAM J. Comput. 17, No. 2, 194-209 (1988). The RSA and Rabin encryption functions \(E_ N(\cdot)\) are respectively defined by raising \(x\in Z_ N\) to the power e (where e is relatively prime to \(\phi\) (N)) and squaring modulo N (i.e., \(E_ N(x)=x^ e(mod N)\), \(E_ N(x)=x^ 2(mod N)\), respectively). We prove that for both functions, the following problems are computationally equivalent (each is probabilistic polynomial-time reducible to the other): (1) Given \(E_ N(x)\), find x. (2) Given \(E_ N(x)\), guess the least-significant bit of x with success probability \(1/2+1/poly(n)\) (where n is the length of the modulus N). This equivalence implies that an adversary, given the RSA/Rabin ciphertext, cannot have a non-negligible advantage (over a random coin flip) in guessing the least-significant bit of the plaintext, unless he can invert RSA/factor N. The proof techniques also yield the simultaneous security of the log n least-significant bits. Our results improve the efficiency of pseudorandom number generation and probabilistic encryption schemes based on the intractability of factoring. Cited in 2 ReviewsCited in 33 Documents MSC: 94A60 Cryptography Keywords:RSA encryption; partial information; Rabin encryption; security; pseudorandom number generation; probabilistic encryption schemes; intractability; factoring PDFBibTeX XMLCite \textit{W. Alexi} et al., SIAM J. Comput. 17, No. 2, 194--209 (1988; Zbl 0644.94011) Full Text: DOI