# The Cryptographic Security of the Sum of Bits

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

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-84-190

June 1984

### http://www.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
*x* when presented with the RSA encryption of
*x*, then there exists a probabilistic algorithm using this oracle to recover
*x* when presented with the RSA encryption of
*x*. 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}, Institution = {EECS Department, University of California, Berkeley}, Year = {1984}, Month = {Jun}, URL = {http://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1984/5971.html %F Berger:CSD-84-190