Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-146 | 21st September 2010 14:53

Homomorphic Encryption: from Private-Key to Public-Key


Authors: Ron Rothblum
Publication: 21st September 2010 16:20
Downloads: 7381


We show that any private-key encryption scheme that is weakly
homomorphic with respect to addition modulo 2, can be transformed
into a public-key encryption scheme. The homomorphic feature
referred to is a minimalistic one; that is, the length of a
homomorphically generated encryption should be independent of the
number of ciphertexts from which it was created. We do not require
anything else on the distribution of homomorphically generated
encryptions (in particular, we do not require them to be
distributed like real ciphertexts). Our resulting public-key
scheme is homomorphic in the following sense. If $i+1$ repeated
applications of homomorphic operations can be applied to the
private-key scheme, then $i$ repeated applications can be applied
to the public-key scheme.

ISSN 1433-8092 | Imprint