On the hardness of the least-signficant bits of the RSA and Rabin functions

Webpage for a paper by Alexi, Chor, Goldreich, and Schnorr


Original Abstract

The RSA and Rabin encryption functions $E_N$ are respectively defined by raising 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): 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.

Material available on-line


Back to either Oded Goldreich's homepage. or general list of papers.