# Limits of Provable Security for Homomorphic Encryption Authors: Andrej Bogdanov, Chin Ho Lee URL: https://eprint.iacr.org/2013/344 ## Abstract We show that public-key bit encryption schemes which support weak (i.e., compact) homomorphic evaluation of any sufficiently “sensitive” collection of functions cannot be proved message indistinguishable beyond AM ∩ coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity. Examples of sensitive collections include parities, majorities, and the class consisting of all AND and OR functions.