Group Homomorphic Encryption: Characterizations, Impossibility Results, and Applications

Frederik Armknecht; Stefan Katzenbeisser; Andreas Peter

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2010/501

Group Homomorphic Encryption: Characterizations, Impossibility Results, and Applications

Frederik Armknecht, Stefan Katzenbeisser, and Andreas Peter

Abstract

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.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. To appear in Designs, Codes and Cryptography
Keywords: Foundations Homomorphic Encryption Public-Key Cryptography IND-CCA1 Security Subgroup Membership Problem k-Linear Problem
Contact author(s): andreas peter @ cantab net
History: 2012-01-06: last of 3 revisions; 2010-09-30: received; See all versions
Short URL: https://ia.cr/2010/501
License: CC BY

BibTeX

@misc{cryptoeprint:2010/501,
      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{https://eprint.iacr.org/2010/501}},
      url = {https://eprint.iacr.org/2010/501}
}