Accession Number : ADA141804

Title :   On the Number of Close-and-Equal 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 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)

Descriptors :   *Combinatorial analysis, *Cryptography, Message processing, Data processing security, Algorithms, Polynomials, Computer communications

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE