On the Number of Close-and-Equal Pairs of Bits in a String (with Implications on the Security of RSA's L.S.B.),
Odcd Goldreich · 1984
We consider the following problem: Let s be a n-bit string with m ones and n - m zeros. Denote by CEt(s) the number of pairs, of equal bits which are within distance t apart, in the string s. What is the minimum value of CEf(-), when the minimum is taken over all n-bit strings which consists of m ones and n - m zeros? We prove a (reasonably) tight lower bound for this combinatorial problem. Implications, on the cryptographic security of the least significant bit of a message encrypted by the RSA scheme, follow. E.g. under the assumption that the RSA is unbreakable; there exist no probabilistic polynomial-time algorithm which guesses the least significant bit of a message (correctly) with probability at least 0.725 , when given the encryption of the message using the RSA. This is the best result known concerning the security of RSA's least significant bit.