Generalized low density lattices for GGH cryptosystem

Goldreich-Goldwasser-Halevi (GGH) is a lattice-based public-key cryptosystem which has been widely developed due to its simple encryption and decryption procedures. Despite many existing GGH improvements, its huge public key size remains its main drawback, which prevents the system from being used in practice. In order to reduce the key size, we propose in this paper a new GGH cryptosystem using Generalized low density (GLD) lattices. For this proposed GGH lattice-based scheme, we provide a security analysis by considering all known attacks on GGH systems. We conclude that our scheme is as secure as the existing GGH schemes. We also investigate the complexity of our cryptosystem and prove that GLD lattices reduce significantly the key size and the complexity of the key generation and decryption phases compared to other GGH systems.