Stronger Security Proofs for RSA and Rabin Bits

The RSA and Rabin encryption function are respectively defined as E_N(x) = xe mod N and E_N(x) = x2 mod N, where N is a product of two large random primes p, q and e is relatively prime to φ(N). We present a much simpler and stronger proof of the result of Alexi, Chor, Goldreich and Schnorr [ACGS88] 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 % MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfKttLearuqr1ngBPrgarmWu51MyVXgatC % vAUfeBSjuyZL2yd9gzLbvyNv2CaeHbd9wDYLwzYbItLDharyavP1wz % ZbItLDhis9wBH5garqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbb % L8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs0-yqaqpe % pae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaaiaabeqaam % aaeaqbaaGcbaWaaSaaaeaacqaIXaqmaeaacqaIYaGmaaGaey4kaSYa % aSaaaeaacqaIXaqmaeaaieaacqWFWbaCcqWFVbWBcqWFSbaBcqWF5b % qEcqGGOaakcqWGUbGBcqGGPaqkaaaaaa!475B! $$ \frac{1} {2} + \frac{1} {{poly(n)}} $$, where N has n bits. The new proof consists of a more efficient algorithm for inverting the RSA/Rabin-function with the help of an oracle that predicts the least-significant bit of x. It yields provable security guarantees for RSA-message bits and for the RSA-random number generator for moduli N of practical size.