RSA and Rabin Functions: Certain Parts are as Hard as the Whole

The RSA and Rabin encryption functions EN () are respectively defined by raising x ZN to the power e (where e is relatively prime to (N) ) and squaring modulo N (i. e. , EN (x) = xᵉ (N), EN (x) = x² (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 EN (x), find x. (2) Given EN (x), guess the least-significant bit of x with success probability 12 + 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 n least-significant bits. Our results improve the efficiency of pseudorandom number generation and probabilistic encryption schemes based on the intractability of factoring.