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