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://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 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://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