[BL13] Limits of Provable Security for Homomorphic Encryption

Authors: Andrej Bogdanov, Chin Ho Lee | Venue: CRYPTO 2013 | Source

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.

BibTeX

Copy

@Inproceedings{C:BogLee13,
  author = {Andrej Bogdanov and Chin Ho Lee},
  title = {Limits of Provable Security for Homomorphic Encryption},
  pages = {111--128},
  editor = {Ran Canetti and Juan A. Garay},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2013, Part~I},
  volume = {8042},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~18--22},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2013},
  doi = {10.1007/978-3-642-40041-4_7},
}