BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20220728T120000Z
UID:43db3e52a3e14bd544b10667089fb00a-309
DTSTAMP:19700101T120010Z
DESCRIPTION:Why we could not prove SETH hardness of CVP for even norms!
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/309/why-we-could-not-prove-seth-hardness-of-cvp-for-even-norms/
SUMMARY:Lattice-based cryptographic schemes have generated much interest in recent years. Their security relies on the computational hardness of problems over geometric objects called lattices. These problems have been used to build advanced cryptographic primitives such as fully homomorphic encryption, and they are believed to be resistant to quantum attacks. Given the recent advancement in quantum technologies, many institutes such as the National Institute of Standards and Technology (NIST) and European Telecommunications Standards Institute (ETSI) have initiated a process for standardization and deployment of lattice-based schemes widely over the next few years. Recently, NIST has announced lattice-based candidates (Kyber and Dilithium) as primary algorithms for implementation.
<br>
The security of the lattice-based cryptosystem schemes crucially relies on the assumption that the best-known algorithms for the corresponding lattice problems cannot be significantly improved. Understanding the fine-grained hardness of these problems is one way of getting more confidence in these assumptions.
<br>
In this talk, I will discuss the fine-grained hardness of the lattice problems in different p-norms. Mainly, I will focus on the recent joint work with Divesh Aggarwal. Under a complexity-theoretic assumption, we show that getting any SETH-hardness for the lattice problems in the even norm is impossible by a poly-time reduction from k-SAT to CVP. We also show similar impossibility results for SUBSET-SUM and many other problems.
DTSTART:20220728T120000Z
END:VEVENT
END:VCALENDAR