Paper 2021/1534

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

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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACNS 2022
Keywords
homomorphic encryptionLWEmatrix operations
Contact author(s)
zhaoliangjapan @ scu edu cn
History
2021-11-22: received
Short URL
https://ia.cr/2021/1534
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1534,
      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{https://eprint.iacr.org/2021/1534}},
      url = {https://eprint.iacr.org/2021/1534}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.