The Shortest Vector Problem in Ideal Lattices

Open Access
Author:
Huynh, Simon
Area of Honors:
Mathematics
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
  • Kirsten Eisentraeger, Thesis Supervisor
  • Mark Levi, Honors Advisor
Keywords:
  • number theory
  • Cryptology
  • mathematics
  • abstract algebra
  • ideal lattices
  • cyclic lattices
  • the Shortest Vector Problem
  • number fields
  • number rings
  • lattices
  • cryptosystems
  • quantum computers
  • RSA
  • Post-quantum Cryptography
Abstract:
In this thesis, we present a study of ideal lattices, their related cryptosystems, and the Shortest Vector Problem. Our main goal is to study whether ideal lattices with added properties will lessen the security measures of the corresponding cryptographic schemes. In our study, we found some examples of cyclic sublattices of Z^n where a shortest vector can be easily computed. The Shortest Vector Problem in lattices plays an important role in Post-Quantum Cryptography. Due to the current rapid advances in the field of quantum computing, some of the currently used cryptosystems can be broken. Therefore, it is an urgent task to develop practical quantum-resistant cryptographic algorithms as replacements for some of the currently used ones like RSA. Among many potential candidates, lattice-based cryptographic schemes are attractive for their strong provable security and resistance to quantum attacks. To improve the practicality of these systems, lattices with additional structures such as cyclic sublattices of Z^n (a special case of general lattices) are employed. The extra properties allow faster computations and less space complexity. However, we have little knowledge about how secure the lattice problems like the Shortest Vector and Closest Vector problems are for them. In fact, there is concern that the added structures will reduce the level of security in these special cases.