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:
- Anne Kirsten Eisentraeger, Thesis Supervisor
Mark Levi, Thesis 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.