Paper 2021/1534

An Optimized GHV-Type HE Scheme: Simpler, Faster, and More Versatile

Liang Zhao, Ze Chen, Liqun Chen, and Xinyi Huang


In this paper we present an optimized variant of Gentry, Halevi and Vaikuntanathan (GHV)'s Homomorphic Encryption (HE) scheme (EUROCRYPT'10). Our scheme is appreciably more efficient than the original GHV scheme without losing its merits of the (multi-key) homomorphic property and matrix encryption property. In this research, we first measure the density for the trapdoor pairs that are created by using Alwen and Peikert's trapdoor generation algorithm and Micciancio and Peikert's trapdoor generation algorithm, respectively, and use the measurement result to precisely discuss the time and space complexity of the corresponding GHV instantiations. We then propose a generic GHV-type construction with several optimizations that improve the time and space efficiency from the original GHV scheme. In particular, our new scheme can achieve asymptotically optimal time complexity and avoid generating and storing the inverse of the used trapdoor. Finally, we present an instantiation that, by using a new set of (lower) bound parameters, has the smaller sizes of the key and ciphertext than the original GHV scheme.

Note: This is the current full version of the paper published at ACNS 2022. We may give a final full version later.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision.ACNS 2022
homomorphic encryptionLWEmatrix operations
Contact author(s)
zhaoliangjapan @ scu edu cn
2021-11-22: received
Short URL
Creative Commons Attribution


      author = {Liang Zhao and Ze Chen and Liqun Chen and Xinyi Huang},
      title = {An Optimized GHV-Type HE Scheme: Simpler, Faster, and More Versatile},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1534},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.