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