Stronger Security proofs for RSA and Rabin Bits

摘要

The RSA and Rabin encryption functions are respectively defined as E_n(x) = x~e mod N and E_n (x)=x~2 mod N, where N is a product of two large Random primes p, q and e is relatively prime to ψ(N). We present a simpler and tighter Proof of the result of alexi et al. [ACGS] that the following problems are equivalent By probabilistic polynomial time reductions: (1) given E_n(x) find x; (2) given E_n (x) Predict the least-significant bit of x with success probability 1/2+1/poly(n), where N has n bits.