GGH may not be dead after all

Abstract

In 1997, Goldreich, Goldwasser and Halevi presented the GGH cryptosystem, which is based on hard lattice problems. Only two years later, Nguyen pointed out major flaws on the scheme. From that point on, the system was considered officially dead. However, in 2012, Yoshino and Kunihiro proposed some improvements on the GGH cryptosystem, claiming to have fixed the flaws pointed out by Nguyen. In this paper, we make a thorough analysis of this tweaked GGH scheme, showing that, in practice, it behaves mostly in the same way as the original scheme. We also propose some modifications that can effectively make the new GGH different from the original one.