Richard Berger and Howard J. Karloff and David B. Shmoys

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-84-190

, 1984

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-190.pdf

We show that if there exists a deterministic oracle that can determine the sum of the bits in the binary representation of <i>x</i> when presented with the RSA encryption of <i>x</i>, then there exists a probabilistic algorithm using this oracle to recover <i>x</i> when presented with the RSA encryption of <i>x</i>. We present a similar result for Rabin encryption.

---

BibTeX citation:

@techreport{Berger:CSD-84-190,
    Author= {Berger, Richard and Karloff, Howard J. and Shmoys, David B.},
    Title= {The Cryptographic Security of the Sum of Bits},
    Year= {1984},
    Month= {Jun},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5971.html},
    Number= {UCB/CSD-84-190},
    Abstract= {We show that if there exists a deterministic oracle that can determine the sum of the bits in the binary representation of <i>x</i> when presented with the RSA encryption of <i>x</i>, then there exists a probabilistic algorithm using this oracle to recover <i>x</i> when presented with the RSA encryption of <i>x</i>. We present a similar result for Rabin encryption.},
}

EndNote citation:

%0 Report
%A Berger, Richard 
%A Karloff, Howard J. 
%A Shmoys, David B. 
%T The Cryptographic Security of the Sum of Bits
%I EECS Department, University of California, Berkeley
%D 1984
%@ UCB/CSD-84-190
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5971.html
%F Berger:CSD-84-190