next up previous
Next: On the Cryptographic Applications Up: The Post-Doctoral Period (1983-86) Previous: On the Number of

RSA/Rabin Functions: Certain Parts are As Hard As the Whole

It is shown that the least significant bit is a hard-core predicate of the RSA and Rabin functions. That is, ability to guess this bit correctly from the value of the function, with non-negligible advantage, yields ability to invert the function. The proof demonstrates one fundamental advantage of certain pairwise-independent sequences over sequences of total independence.


\fbox{\begin{minipage}{40em}
{\bf Abstract ({rev.}):} {The RSA and Rabin functi...
...on schemes that
are based on the intractability of factoring.}
\end{minipage}}


Comments: Authored by W. Alexi, B. Chor, O. Goldreich and C. P. Schnorr. Appeared in



Oded Goldreich
2003-07-30