Cryptology ePrint Archive: Report 2010/501

Group Homomorphic Encryption: Characterizations, Impossibility Results, and Applications

Frederik Armknecht and 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.

Category / Keywords: Foundations, Homomorphic Encryption, Public-Key Cryptography, IND-CCA1 Security, Subgroup Membership Problem, k-Linear Problem

Publication Info: To appear in Designs, Codes and Cryptography

Date: received 29 Sep 2010, last revised 6 Jan 2012

Contact author: andreas peter at cantab net

Available format(s): PDF | BibTeX Citation

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

Version: 20120106:104554 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]