Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there an encyption scheme that combines additive homomorphism with ability to proxy re-encrypt? I've tried digging around on the Internet but haven't found anything conclusive on the topic.

share|improve this question
Craig Gentry's full-homomorphic scheme is a one-time multi-use proxy-reencrypt scheme (in fact, it is this property that allows him to 'bootstrap' the scheme). It's far from efficient, however, although there is a great deal of research into making it so. – Reid Oct 21 '13 at 1:40
up vote 2 down vote accepted

The schemes by AFGH in this paper are pairing based ElGamal type non-interactive, single-use (single-hop) and unidirectional IND-CPA secure proxy re-encryption schemes.

Although by their construction they are multiplicatively homomorphic (the authors do not mention it in the paper, but it works analogously to ElGamal), you can use the same trick as in "exponential ElGamal" to make them additively homomorphic.

This means that you represent the message $m$ to be encrypted as power of the generator $g$ of the target group ($G_2$ in their paper), i.e., as $g^m$ for messages in $Z_p$ (with $p$ being the order of the prime order group). Then, you are, however, limited to "small" message spaces as decrypting involves computing discrete logs in $G_2$. I do not know your application, but in many scenarios that should be sufficient.

As far as I know it has never been used in this context and there are no papers I am aware of that use additively homomorphic proxy re-encryption.

There may also be other schemes (as the one from INDOCRYPT 2013 pointed out by xagawa - however, this scheme is multi-hop - which may render it impractical for some applications but may allow others not feasible with one-hop schemes), but this one should be a good starting point. As already stated by Reid, Gentry's scheme can also be used for that, but fully homomorphic encryption schemes are not yet practically efficient.

share|improve this answer
That's really helpful. Thanks! – Martin Sustrik Oct 21 '13 at 7:55

Very recently, Yoshinori Aono, Xavier Boyen, Le Trieu Phong, and Lihua Wang (INDOCRYPT 2013) proposed an additively-homomorphic proxy re-encryption scheme from lattices, which is multi-hop, unidirectional, and CPA-secure. They reported that their scheme is faster than the AFGH05 scheme.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.