On the Number of Close-and-Equal Pairs of Bits in a String (with Implications on the Security of RSA's L.S.B.),
Abstract
This document considers the following problem: Let s be a n-bit string with m ones and n-m zeros. Denote by CE sub t(s) the number of pairs, of equal bits which are within distance t apart, in the string s. What is the minimum value of CE sub t(.), when the minimum is taken over all n-bit strings which consists of m ones and n - m zeros? The author proves 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 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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1984
- Accession Number
- ADA141804
Entities
People
- O. Goldreich
Organizations
- Massachusetts Institute of Technology