The Cryptographic Security of the Sum of Bits
Richard J. Berger, Howard J. Karloff, David B. Shmoys · 1984
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