Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-156 | 5th June 2013 07:21

Limits of provable security for homomorphic encryption

RSS-Feed




Revision #1
Authors: Andrej Bogdanov, Chin Ho Lee
Accepted on: 5th June 2013 07:21
Downloads: 3212
Keywords: 


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.



Changes to previous version:

New result on rerandomization from strong homomorphic evaluation; more general framework; revisions in introduction and references to related work


Paper:

TR12-156 | 12th November 2012 04:55

Limits of provable security for homomorphic encryption


Abstract:

We show that public-key bit encryption schemes which support weak homomorphic evaluation of parity or majority cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity.

Previous works on the limitation of reductions for proving security of encryption schemes make restrictive assumptions about the encryption algorithm (Brassard, Goldreich and Goldwasser, Akavia et al.) or about the reduction (Feigenbaum and Fortnow, Bogdanov and Trevisan, Akavia et al.) Our first result makes no assumptions of either sort.

Towards these results, we show that any homomorphic evaluator for parity or majority over sufficiently many inputs can be converted 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.



ISSN 1433-8092 | Imprint