
Accession Number : ADA141804
Title : On the Number of CloseandEqual Pairs of Bits in a String (with Implications on the Security of RSA's L.S.B.),
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Personal Author(s) : Goldreich,O
PDF Url : ADA141804
Report Date : Mar 1984
Pagination or Media Count : 23
Abstract : This document considers the following problem: Let s be a nbit string with m ones and nm 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 nbit 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 polynomialtime 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)
Descriptors : *Combinatorial analysis, *Cryptography, Message processing, Data processing security, Algorithms, Polynomials, Computer communications
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE