Foundations of Lattice-based Cryptography


Rajendra Kumar February 24, 2023.


Public key cryptography is essential for internet security, and RSA and Diffie-Hellman are the most widely used public-key cryptosystems for internet traffic. However, recent progress in building quantum computers threatens RSA and Diffie-Hellman’s security, as they are vulnerable to quantum adversaries. To address this, organizations like the National Institute of Standards and Technology (NIST) and the European Telecommunications Standards Institute (ETSI) have started standardizing and deploying cryptosystems that are secure against quantum attacks. Recently, NIST has chosen Kyber and Dilithium, lattice-based candidates, as primary algorithms for security against quantum adversaries. The security of these cryptosystems crucially relies on the assumption that the best-known algorithms for the lattice problems cannot be significantly improved.

In this talk, I will discuss the connections between the security of lattice-based cryptosystems and the hardness of lattice problems. I will talk about classical and quantum algorithms for lattice problems. I will also discuss the works on the fine-grained security of lattice-based Crypto.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Why we couldn't prove SETH hardness of CVP for even norms, Subset-SUM, and Many more!
  • Are quantum speedups for learning expressive classes possible?
  • Polynomial Time Byzantine Agreement with Optimal Resilience
  • Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
  • Algorithms and Barriers for Fast Matrix Multiplication