On the smallest-basis problem underlying the GGH lattice-based cryptosystem - Mandangan, Arif; Kamarulhaili, Hailiza; Asbullah, Muhammad Asyraf (Institute for Mathematical Research, Universiti Putra Malaysia, 2019)
The security of the Goldreich-Goldwasser-Halevi (GGH) cryptosystem is relying on the Smallest-Basis Problem (SBP) and the Closest-Vector Problem (CVP) instances. Previously, these instances were just implicitly mentioned and discussed without any proper definition. In this paper, we explicitly defined the underlying SBP instance that arose from the GGH cryptosystem. From that, we showed how the solution to these problems could be obtained and how the obtained solutions could lead to the security breach in the GGH cryptosystem. Finally, we proposed some possible strategies for strengthening the security of the GGH cryptosystem.