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
-
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},
url = {https://eprint.iacr.org/2021/1534}
}
