Paper 2019/062

Additively Homomorphic IBE from Higher Residuosity

Michael Clear and Ciaran McGoldrick


We present an identity-Based encryption (IBE) scheme that is group homomorphic for addition modulo a ``large'' (i.e. superpolynomial) integer, the first such group homomorphic IBE. Our first result is the construction of an IBE scheme supporting homomorphic addition modulo a poly-sized prime $e$. 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. We also show that our scheme for $e > 2$ is anonymous by additionally assuming the hardness of deciding solvability of a special system of multivariate polynomial equations. We provide a justification for this assumption by considering known attacks.

Available format(s)
Publication info
Published by the IACR in PKC 2019
Identity-Based EncryptionHomomorphic Encryption
Contact author(s)
clearm @ tcd ie
Ciaran McGoldrick @ scss tcd ie
2019-01-25: received
Short URL
Creative Commons Attribution


      author = {Michael Clear and Ciaran McGoldrick},
      title = {Additively Homomorphic IBE from Higher Residuosity},
      howpublished = {Cryptology ePrint Archive, Paper 2019/062},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.