Talks - Fall 2018

SVP

Title

Speaker

Date

Time

Venue

Abstract

Hardness of Lattice Problems

Rajendra Kumar

25th August 2018

12:15-1:15 PM

KD102

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.

References:

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)

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator