Limits of provable security for homomorphic encryption

Andrej Bogdanov; Chin Ho Lee

Paper 2013/344

Limits of provable security for homomorphic encryption

Andrej Bogdanov and Chin Ho Lee

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 intersect 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. Our techniques also give a method for converting a strong (i.e., distribution-preserving) homomorphic evaluator for essentially any boolean function (except the trivial ones, the NOT function, and the AND and OR functions) into a rerandomization algorithm: This is a procedure that converts a ciphertext into another ciphertext which is statistically close to being independent and identically distributed with the original one. Our transformation preserves negligible statistical error.

Note: Also posted as ECCC report TR12-156

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. This is a long version of a CRYPTO 2013 paper
Keywords: proofs of security homomorphic encryption rerandomization
Contact author(s): andrejb @ cse cuhk edu hk
History: 2013-06-09: received
Short URL: https://ia.cr/2013/344
License: CC BY

BibTeX

@misc{cryptoeprint:2013/344,
      author = {Andrej Bogdanov and Chin Ho Lee},
      title = {Limits of provable security for homomorphic encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2013/344},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/344}},
      url = {https://eprint.iacr.org/2013/344}
}