Improving GGH Public Key Scheme Using Low Density Lattice Codes
This work addresses efficiency and security issues in lattice-based cryptography, which is important for cryptographic applications, but it is incremental as it builds on existing GGH and LDLC frameworks.
The paper tackles the large public key length and low security level of the GGH public key cryptosystem by introducing a new cryptosystem based on Low Density Lattice Codes (LDLCs), resulting in reduced key length and decryption complexity, enabling the use of bigger security parameters and resistance to efficient attacks.
Goldreich-Goldwasser-Halevi (GGH) public key cryptosystem is an instance of lattice-based cryptosystems whose security is based on the hardness of lattice problems. In fact, GGH cryptosystem is the lattice version of the first code-based cryptosystem, proposed by McEliece. However, it has a number of drawbacks such as; large public key length and low security level. On the other hand, Low Density Lattice Codes (LDLCs) are the practical classes of lattice codes which can achieve capacity on the additive white Gaussian noise (AWGN) channel with low complexity decoding algorithm. This paper introduces a public key cryptosystem based on LDLCs to withdraw the drawbacks of GGH cryptosystem. To reduce the key length, we employ the generator matrix of the used LDLC in Hermite normal form (HNF) as the public key. Also, by exploiting the linear decoding complexity of the used LDLC, the decryption complexity is decreased compared with GGH cryptosystem. These increased efficiencies allow us to use the bigger values of security parameters. Moreover, we exploit the special Gaussian vector whose variance is upper bounded by the Poltyrev limit as the perturbation vector. These techniques can resist the proposed scheme against the most efficient attacks to the GGH-like cryptosystems.