Cryptology ePrint Archive: Report 2021/1534

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

Liang Zhao and Ze Chen and 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.

Category / Keywords: public-key cryptography / homomorphic encryption, LWE, matrix operations

Original Publication (with major differences): ACNS 2022

Date: received 19 Nov 2021

Contact author: zhaoliangjapan at scu edu cn

Available format(s): PDF | BibTeX Citation

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

Version: 20211122:113057 (All versions of this report)

Short URL: ia.cr/2021/1534


[ Cryptology ePrint archive ]