Attribute-Based Group Homomorphic Encryption and Additively Homomorphic IBE

Abstract

Group Homomorphic Encryption (GHE), formally defined by Armknecht, Katzenbeisser and Peter, is a public-key encryption primitive where the decryption algorithm is a group homomorphism. Hence it suports homomorphic evaluation of a single algebraic operation such as modular addition or modular multiplication. Most classical homomorphic encryption schemes such as as Goldwasser-Micali and Paillier are instances of GHE. In this work, we extend GHE to the attribute-based setting. We introduce and formally define the notion of Attribute-Based GHE (ABGHE) and explore its properties. Our main result is the construction of an Identity-Based Encryption (IBE) scheme supporting homomorphic addition modulo a poly-sized prime ee, which is an instance of ABGHE. Our construction builds upon the IBE scheme of Boneh, LaVigne and Sabin (BLS). BLS relies on a hash function that maps identities to e^th residues. However there is no known way to securely instantiate such a function. Our construction extends BLS so that it can use a hash function that can be securely instantiated. We prove our scheme IND-ID-CPA secure under the (slightly modified) e^th residuosity assumption in the random oracle model and show that it supports a (modular) additive homomorphism. By using multiple instances of the scheme with distinct primes and leveraging the Chinese Remainder Theorem, we can support homomorphic addition modulo a ``large'' (i.e. superpolynomial) integer, the first such IBE scheme. We also show that our scheme for e > 2e>2 is anonymous assuming the hardness of deciding solvability of a special system of multivariate polynomial equations. Finally, we define a primitive for attribute-based group homomorphisms in the multi-key setting, introduce an important security property and present a generic construction of the primitive meeting this security property.