Malaysian Journal of Mathematical Sciences, August 2019, Vol. 13(S)
Special Issue: The 6th International Cryptology and Information Security Conference (CRYPTOLOGY2018)
On the Smallest-Basis Problem underlying the GGH Lattice-based Cryptosystem
Mandangan, A., Kamarulhaili, H. and Asbullah, M. A.
Corresponding Email: [email protected]
Received date: -
Accepted date: -
Abstract:
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.
Keywords: GGH cryptosystem, Smallest-Basis Problem, Closest-Vector Problem, Shortest-Vector Problem
