Seminars

View all Seminars  |  Download ICal for this event

Why we could not prove SETH hardness of CVP for even norms!

Series: Department Seminar

Speaker: Dr. Rajendra Kumar,Research fellow,Divesh Aggarwals group, Center for Quantum Technologies, NUS

Date/Time: Jul 28 10:00:00

Location: CSA Conference Room, (Room No. 311, Second Floor)

Abstract:
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.

Speaker Bio:
Rajendra Kumar is a Research fellow in Divesh Aggarwals group at the Center for Quantum Technologies, NUS. He completed his Ph.D. under the Joint degree program of the Indian Institute of Technology, Kanpur, and the National University of Singapore. He is broadly interested in algorithms and cryptography, with special interests in lattice algorithms and reductions. More information can be found on his homepage: https://sites.google.com/view/rajendrak/.

Host Faculty: Prof. Bhavana Kanukurthi