Techniques for Solving Shortest Vector Problem

• Published in: International journal of advanced computer science & applications 2021, Vol.12 (5)
• Main Authors: Reddy, V. Dinesh, Ravi, P., Abdul, Ashu, Morampudi, Mahesh Kumar, Bojjagani, Sriramulu
• Format: Article
• Language: English
• Subjects: Algorithms; Communication theory; Cryptography; Lattices; Optimization; Quantum computers; Surface hardness
• ISSN: 2158-107X; 2156-5570
• DOI: 10.14569/IJACSA.2021.0120598

Lattice-based crypto systems are regarded as secure and believed to be secure even against quantum computers. lattice-based cryptography relies upon problems like the Shortest Vector Problem. Shortest Vector Problem is an instance of lattice problems that are used as a basis for secure cryptographic schemes. For more than 30 years now, the Shortest Vector Problem has been at the heart of a thriving research field and finding a new efficient algorithm turned out to be out of reach. This problem has a great many applications such as optimization, communication theory, cryptography, etc. This paper introduces the Shortest Vector Problem and other related problems such as the Closest Vector Problem. We present the average case and worst case hardness results for the Shortest Vector Problem. Further this work explore efficient algorithms solving the Shortest Vector Problem and present their efficiency. More precisely, this paper presents four algorithms: the Lenstra-Lenstra-Lovasz (LLL) algorithm, the Block Korkine-Zolotarev (BKZ) algorithm, a Metropolis algorithm, and a convex relaxation of SVP. The experimental results on various lattices show that the Metropolis algorithm works better than other algorithms with varying sizes of lattices.