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):
- (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.
Material available on-line
- final
version, SICOMP, Vol. 17, No. 2, April 1988. (Copyright of SIAM)
Back to
either Oded Goldreich's homepage.
or general list of papers.