Research Projects

Public key cryptography (PKC) is a key primitive of modern cryptography. Almost all security protocols crucially rely on this primitive. RSA and Diffie-Hellman are the most well-known PKC algorithms, and more than half of the internet traffic relies on them for security. Unfortunately, these two number-theoretic cryptosystems are not secure if adversaries gain access to a quantum computer. Seeing the rapid progress in the design of quantum computers, we cannot deny the possibility of having a functional quantum computer in a couple of decades. Looking at this threat, the goal is to design cryptosystems that can be implemented on our current computers but also provide security even when adversaries have access to quantum computers. Lattice-based cryptosystems are the most promising candidates for post-quantum security. Some of these lattice-based cryptosystems will be deployed all over the internet in the next 3–5 years. The aim of this project is to analyze the security of lattice-based cryptosystems against adversaries with access to quantum computers. In the attached technical file, we provide a brief description of known results and gaps in the security analysis. We will also give a concise research plan to bridge these gaps. A lattice is a mathematical object. Given a set of linearly independent vectors (basis), the points that can be generated by their integer linear combinations form a lattice. Initial work on lattice-based cryptosystems started with the motivation of designing cryptosystems whose security can be based on the worst-case hardness of a computational problem. Later, it became more interesting due to their conjectured security against quantum computers. The security of lattice-based cryptography relies on the worst-case hardness of approximating the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices. In this project, we plan to design faster quantum algorithms for SVP and CVP. We also plan to determine the concrete quantum hardness of these problems. The goal of these results is to help us find better parameters for lattice-based cryptosystems with provable security. This line of work requires urgency, as very soon lattice-based cryptosystems will be deployed all over the internet. Before this happens, we want to ensure we are confident about the parameters we choose for these cryptosystems. We aim to rule out the possibility of any surprising algorithmic results on these problems by providing concrete lower bounds for them.