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.

  • $\begingroup$ 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. $\endgroup$
    – Reid
    Oct 21, 2013 at 1:40

2 Answers 2


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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