×

RSA and Rabin functions: Certain parts are as hard as the whole. (English) Zbl 0644.94011

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.

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI