A New Countermeasure to Combat the Embedding-Based Attacks on the Goldreich-Goldwasser-Halevi Lattice-Based Cryptosystem

Abstract

Despite being considered the first practical lattice-based cryptosystem, interest from the post-quantum cryptography society in the Goldreich-Goldwasser-Halevi (GGH) lattice-based cryptosystem drastically drop due to the embedding-based attacks. The attacks successfully simplified the underlying Closest-Vector Problem (CVP) and made the security of the scheme broken. The attacks become noxious to the GGH cryptosystem due to its ability to simplify the underlying CVP which triggered the enlargement of lattice gaps. Consequently, the simplified CVP can be reduced to a Shortest-Vector Problem (SVP) variant which can be solved by using lattice-reduction algorithms such as the LLL algorithm in a shorter amount of time. The simpler way to evade from these attacks is by implementing larger lattice dimensions which immediately reduce the efficiency of this scheme. Recently, an improved version of the GGH cryptosystem, namely the GGH-MKA cryptosystem, has been proven immune to the embedding-based attacks. The improvement is made by preventing the simplification of the underlying CVP. For that purpose, an error vector   is introduced. The error vector is non-eliminable and at the same time maintains the lattice gap. Consequently, the underlying CVP remains in its original form without being simplified. In this study, we showed that the error vector   is not unique. We proposed another error vector   to combat the embedding-based attacks. We proved that the new error vector    has similar capabilities in terms of preventing the simplification of the underlying CVP and maintaining the lattice gap. By improving the security of the GGH cryptosystem, more interest from the mainstream post-quantum discussion could be redirected to the scheme to make it competent and relevant again.