The security of individual RSA bits

Abstract

We study the security of individual bits in an RSA encrypted message E/sub N/(X). We show that given E/sub N/(X), predicting any single bit in x with only a non-negligible advantage over the trivial guessing strategy is (through a polynomial time reduction) as hard as breaking RSA. We briefly discuss a related result for bit security of the discrete logarithm.