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

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.

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

*Proc. of the 25th FOCS*, 1984, pp. 449-457.
(partial result w/ B. Chor only),
*Crypto84 (Proceedings)*,
Lecture Note in Computer Science (196)
Springer Verlag, pp. 303-313, 1985.
*SIAM Jour. on Comp.*,
Vol. 17, No. 2, April 1988, pp. 194-209.

*Oded Goldreich*

*2003-07-30*