Goldreich-Goldwasser-Halevi (GGH) cryptosystem is the first lattice-based encryption scheme that was considered practical. Its inventors conjectured that the underlying Closest Vector Problem (CVP) instance which arose from the scheme was intractable when the cryptosystem is implemented in lattice with a dimension larger than 200. This conjecture was based on the results of thorough experiments and analyses on its security. By directly solving the underlying CVP instance, the tested attacks failed once the implemented lattice dimension is larger than 110. Unfortunately, the GGH cryptosystem is now considered broken due to a devastating attack on it which is able to break the security of the scheme even when it is implemented in lattice with a dimension larger than 200. The attack is referred to as Nguyen’s attack. Instead of directly solving the underlying CVP instance, the Nguyen’s attack is managed to simplify the instance and solved the simplified version of the instance which is much easier than the original instance. In this paper, we proposed a strategy which could thwart the simplification stage of the Nguyen’s attack. We proved that the GGH cryptosystem with a standard threshold parameter = 3 could survive against the Nguyen’s attack by applying the proposed strategy. To maintain the security dependency on the underlying CVP instance which was experimentally shown and analyzed to be invulnerable to some significant attacks, the proposed strategy only involves minimal modifications on the original setup of the GGH cryptosystem. With its great simplicity and practicality, the improved GGH cryptosystem could be reconsidered as one of the most promising lattice-based encryption schemes in the post-quantum cryptography realm.
Volume 12 | 02-Special Issue
Pages: 832-839
DOI: 10.5373/JARDCS/V12SP2/SP20201140