Paper 2010/501

Group Homomorphic Encryption: Characterizations, Impossibility Results, and Applications

Frederik Armknecht, Stefan Katzenbeisser, and Andreas Peter


We give a complete characterization both in terms of security and design of all currently existing group homomorphic encryption schemes, i.e., existing encryption schemes with a group homomorphic decryption function such as ElGamal and Paillier. To this end, we formalize and identify the basic underlying structure of all existing schemes and say that such schemes are of shift-type. Then, we construct an abstract scheme that represents all shift-type schemes (i.e., every scheme occurs as an instantiation of the abstract scheme) and prove its IND-CCA1 (resp. IND-CPA) security equivalent to the hardness of an abstract problem called Splitting Oracle-Assisted Subgroup Membership Problem, SOAP (resp. Subgroup Membership Problem, SMP). Roughly, SOAP asks for solving an SMP instance, i.e., for deciding whether a given ciphertext is an encryption of the neutral element of the ciphertext group, while allowing access to a certain oracle beforehand. Our results allow for contributing to a variety of open problems such as the IND-CCA1 security of Paillier's scheme, or the use of linear codes in group homomorphic encryption. Furthermore, we design a new cryptosystem which provides features that are unique up to now: Its IND-CPA security is based on the k-linear problem introduced by Shacham, and Hofheinz and Kiltz, while its IND-CCA1 security is based on a new k-problem that we prove to have the same progressive property, namely that if the k-instance is easy in the generic group model, the (k+1)-instance is still hard.

Note: Added the notion of shift-type group homomorphic encryption and adapted all results.

Available format(s)
Publication info
Published elsewhere. To appear in Designs, Codes and Cryptography
FoundationsHomomorphic EncryptionPublic-Key CryptographyIND-CCA1 SecuritySubgroup Membership Problemk-Linear Problem
Contact author(s)
andreas peter @ cantab net
2012-01-06: last of 3 revisions
2010-09-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Frederik Armknecht and Stefan Katzenbeisser and Andreas Peter},
      title = {Group Homomorphic Encryption: Characterizations, Impossibility Results, and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2010/501},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.