Hardness of Lattice Problems
25th August 2018
In this talk,we will focus on two fundamental problems in Lattice Theory,
First one is Shortest Vector Problem (SVP) where we find shortest non-zero
vector in Lattice. The other one is Closet Vector Problem (CVP) where we
find closet Lattice point of a given vector. These problems have
applications in Integer Factorization, post-Quantum Cryptography. Security
of the lattice-based cryptosystem is based on the hardness of these
problems. We will show that both the problems are NP-hard within some
constant approximation factor.
No prior knowledge related to lattice is required.
1)Arora, S., Babai, L., Stern, J., and Sweedyk, Z. (1993, November). The
hardness of approximate optima in lattices, codes, and systems of linear
equations. In Foundations of Computer Science, 1993. Proceedings., 34th
Annual Symposium on (pp. 724-733). IEEE.
2) D. Micciancio
The shortest vector problem is NP-hard to approximate to within some
constant. SIAM Journal on Computing 30(6):2008-2035 (March 2001)