Meet a CQTian: Divesh Aggarwal

Divesh Aggarwal, recipient of the NRF Investigatorship, Class of 2024, has a joint appointment with the Centre for Quantum Technologies and the National University of Singapore's School of Computing

You’ve been a Principal Investigator at CQT since 2016. How did you come to work here? 

I was hired not because I'm an expert in quantum computing, but because I work on lattices. Lattice-based cryptosystems have been regarded in recent years as the most promising candidate for post-quantum cryptosystems. There's nothing inherently quantum about lattice-based cryptography; it's just that based on our current understanding of quantum computing, lattice-based cryptosystems are considered resistant to quantum attacks. Interestingly, in the past few years, there have been some claims of quantum algorithms that come tantalisingly close to breaking lattice-based cryptography. Fortunately for cryptographers, these claims were found to be incorrect. 

I am also an Associate Professor in the Department of Computer Science at NUS School of Computing. 

Where did your interest in lattices start? 

I got interested in number theory in high school and started my PhD in number theoretic cryptography. During my PhD, I realised that most problems in number-theoretic cryptography had either been solved or were extremely hard. There were a lot of developments around that time in fully homomorphic encryption, which all used lattice-based cryptography. So, it was a very natural transition for me from number theory to lattices. I began reading a lot of literature on lattices in computer science during my PhD. After my PhD, I joined New York University and was very fortunate to work as a postdoc with Oded Regev, a pioneer in the field. 

Tell us more about how lattice-based cryptography became interesting to people. 

The theoretical cryptography community has been interested in lattices for almost three decades. This interest began well before lattice-based cryptography was considered one of the main candidates for post-quantum cryptography. The initial interest was primarily due to the unique attribute of lattice-based cryptography — worst-case to average-case reductions. This concept is not easy to explain in layman's terms, but let me try. 

Consider the most popular cryptosystem, RSA. Its security relies on the hardness of factoring a number into prime factors. Even if you accept that integer factorisation is hard, it doesn't mean that the specific product of two primes chosen as the key for RSA comes from a distribution of numbers that is hard to factor. 

Say you are given two 40 digit primes 6242950767904892547110745313203633592441 and 5772156649015328606065120900824024310421. The RSA key is just a product of these two primes. 

Is this secure? There could be some way of figuring out this factorisation and then hard-coding the solution for any attacker. Similarly, maybe an attacker could come up with a clever algorithm that is able to factor many numbers and hope that when you take the RSA key at random, it will be one of the numbers that the attacker can factor. 

In order to guarantee that such an attack is very difficult, we can hope that there is a mathematical proof that if an attacker can factor many numbers, then an attacker can factor all numbers. 

This translates to: if I am willing to believe that there is no attacker that factors all numbers, then I can conclude that there is no attacker that succeeds in factoring many numbers. 

Such a guarantee doesn’t exist for RSA, but for lattices, we have such a guarantee. 

For lattice-based cryptography, it was mathematically proven that if there is no algorithm that solves the underlying computational lattice problem, then there is no algorithm that breaks the corresponding crypto scheme. 

You have received an NRF Investigatorship, Class of 2024, for work in this area. Congratulations! What is your project about? 

The proposal is to try and understand lattice-based cryptography better from a theoretical point of view. 

One of the questions I propose to explore is the following: the worst-case to average-case reduction is one of the main advantages of lattice-based cryptography, but when these cryptosystems began to be used in practice over the last 10 years, it received some criticism. This reduction is very effective in theory, but there is a huge loss in the parameters when deriving security estimates for the cryptosystems based on the worst-case to average-case reductions. That means that you get mild security even if you make very strong assumptions about the worst-case lattice problems. My project aims to address this concern and thereby obtain more fine-grained security guarantees for lattice-based cryptography under reasonable assumptions based on our current understanding of computational complexity. 

I have some ideas towards this in my proposal. The research is intended to be high risk, high reward. My hope is that even partial success in any of these endeavours would be sufficiently rewarding for the crypto community. 

How hopeful are you for lattice-based cryptography? 

It's always an ongoing challenge in cryptography. Unfortunately, we are always relying on assumptions that can be broken in the future. So, we just try to be as sure as possible. As cryptographers often say, “Cryptographers seldom sleep well.” 

Are you hiring more people to help? 

Currently, my group includes a senior researcher, two postdocs, and two students close to graduating. The group will be growing significantly next year. 

What do you do when you are not doing research or trying to catch up on sleep? 

Lots of activities — to name a few, playing tennis, squash, board games, bridge, reading, watching movies, watching stand-up