Group homomorphic encryption: characterizations, impossibility results, and applications

Frederik Armknecht, Stefan Katzenbeisser, Andreas Peter

    Research output: Contribution to journalArticleAcademicpeer-review

    32 Citations (Scopus)
    96 Downloads (Pure)


    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.
    Original languageEnglish
    Pages (from-to)209-232
    Number of pages24
    JournalDesigns, codes and cryptography
    Issue number2
    Publication statusPublished - May 2013


    • SCS-Cybersecurity
    • Impossibility results
    • Characterization
    • Homomorphic
    • Encryption
    • Applications
    • n/a OA procedure


    Dive into the research topics of 'Group homomorphic encryption: characterizations, impossibility results, and applications'. Together they form a unique fingerprint.

    Cite this