Alex Carchidi:
Hi! So, I'm Alex, and I'm here for Quantum Canary with Dr. Khanh Nguyen from the King's College of London. So, Khanh, how's it going this morning?
Ngoc Khanh Nguyen:
Good, good. The weather is not bad, it's not rainy, so that's a plus. How are you?
Alex:
I'm great, and I am eager to talk about lattice cryptography with you. But before we do, to begin, could you briefly introduce yourself and tell us a bit about your background? How you came to be in cryptography and what drew you specifically towards lattice cryptography.
Khanh:
Right, right, so brief background. Since 2023, I'm an assistant professor at King's College London. I mainly work on lattice-based zero-knowledge proofs and snarks, as well as applications to privacy-preserving primitives, such as advanced signatures, anonymous credentials.
I studied maths and computer science at the University of Bristol. That's when I learned about cryptography, and more interestingly, that's when I learned that to prove security of a cryptographic scheme, what you do is that you provide a mathematical proof, or in other words, a reduction. In most cases, to show that it's secure under some mathematical hard problem.
Yeah, so I was very interested in this area, because it combines maths and CS and it's very practical and useful in real life. I wanted to follow this path, and because I was also interested in number theory, I did a quick search to see the areas in cryptography, and I noticed lattice cryptography, which is exactly the intersection of what I'm interested in.
“What does it mean that a cryptographic scheme is secure, say, in the public key setting? It means that if there is an efficient adversary which can break the scheme, then there exists an efficient adversary which can break some underlying hard problem.”
This was one of my main reasons why I wanted to do a PhD at IBM Research Zurich under the supervision of Dr. Vadim Lyubashevsky, apart from the location—Zurich is a lovely city. Vadim and the team at IBM are leading experts in lattice cryptography. They were involved in the submission of Falcon and Dilithium to the NIST standardization process, so I learned a lot from my experience there. Since then, I've been working on lattices.
Alex:
Cool. So, we have kind of a blended audience of people who are technical and those who are more like investors. So, for the more technical curious audience—maybe they don't work with cryptography every day—what would you say lattice cryptography is in simple terms to them?
Khanh:
Yes, it is a very interesting question, and that's a question that during family gatherings, some people ask me, like, “so what is a lattice”, this fundamental question? I find it always tricky to answer, but I'll try my best.
A simple example is; imagine you have a grid of points on a two-dimensional plane. Informally, you can call it a two-dimensional lattice. An interesting problem in lattices is [that] if you're given a target point in this 2D plane, the goal is to find the closest point of the grid to this target.
So if I bring you the paper,draw the grid of the points and I show you the target. With your finger, you can pick, you can tell me which point of the grid is the closest, right? In two dimensions, it's pretty simple; things get pretty hard when you move to, say, thousands.
So this problem that I described is called the closest vector problem; basically, given a target, you have to find a point on the grid which is the closest. How can it be used to build cryptography on top of it? The fundamental question is, okay, you have a grid of points; there can be infinitely many of them. So how do you represent that, right? Because I can't write down all these points on paper, for example.
So you represent them using a so-called basis. Okay, so a lattice can be represented with a basis, but you can have multiple bases for the same lattice. And actually, for some bases, you could solve this closest vector problem efficiently, but for most other bases, you cannot. So then, this already has some flavor of cryptography. So, our secret key will be the good basis for the lattice, and the public key will be the bad basis for the lattice.
Alex:
So now that we kind of have the basis for what lattice cryptography is, can you explain a little bit about when people say lattice cryptography is quantum secure, what kind of claim is being made there, and what is your unique insight relative to that little world there?
Khanh:
Good, good. So what does it mean that a cryptographic scheme is secure, say, in the public key setting? It means that if there is an efficient adversary which can break the scheme, then there exists an efficient adversary which can break some underlying hard problem.
We consider problems which we believe are hard to break; the common problems which people know, for example, the factoring problem, RSA problem, which people believe is hard for classical computers to solve. The situation changes when we consider quantum computers. With lattice cryptography, we believe there are certain computational problems which are hard; not only for classical, but also for quantum computers.
When we say that “lattice cryptography is post-quantum secure,” we mean that— [with] a few caveats here and there — the lattice-based scheme relies on the lattice computational assumption, which we believe is [difficult for] quantum computers.
Alex:
So, could you tell us a little bit about what you are working on now as it pertains to these problems, and what your ideas are.
Khanh:
Yes. So I work on lattice-based zero-knowledge proofs. So, just so that we're on the same page, a zero-knowledge proof is a protocol between a prover and a verifier. The prover wants to prove the validity of some statement. So, for example, the prover wants to prove that they are over 18 to prove that they're eligible for a driving license, or something like that, and we want to prove that “in zero knowledge”.
“I agree that we see more and more countries pushing for the post-quantum migration. A lot of funding coming into quantum research, and quantum computers are becoming more and more powerful.”
In zero knowledge, the protocol doesn't reveal any sensitive information about the prover. For example, if I want to prove I'm over 18, the protocol shouldn't reveal any information about my date of birth or my residential address.
So what I work on is on lattice-based zero-knowledge proofs—meaning that the security of a zero-knowledge proof, in particular, zero knowledge—rely on lattice assumptions. These lattice assumptions could be, for example, of the same flavor as the closest vector problem I sketched out before.
Zero-knowledge proof is a very general area; one direction is to prove generic arithmetic circuits. For that, we have snarks, but for certain applications, you may want to tailor your zero-knowledge proof to prove very specific statements.
Okay, for example, we have Falcon and Dilithium [that is] either standardized or in the process of being standardized. For certain applications, such as anonymous credentials, you may want to, instead of providing the signature —for example, Falcon and Dilithium— you would want to prove that you possess a signature in zero knowledge. Because Falcon and Dilithium are already lattice-based, it is very natural to apply a lattice-based zero-knowledge proof on top to prove this statement because they belong to the same family, same area.
This is also a very important application. I usually work on these two areas, so one is more general, so proving generic arithmetic circuits, but then, on the other hand, focusing on very specific applications to gain best efficiency.
Alex:
Cool. So, on the topic of Falcon and Dilithium, how should people be thinking about Falcon and Dilithium? Should they be thinking, these are competing schemes, or complementary in some way, or just two options that are kind of neutral? What's the proper way to frame the fact that there's two potential roads to take here?
Khanh:
In this case, we have a signature scheme, and a signature scheme can have multiple efficiency properties. It is not only just the signature size, but it could be the public key size, secret key size, and also the running time.
So, how to start? So let me briefly discuss the two schemes first.
Dilithium can be described as follows; suppose we have a zero-knowledge proof between a prover and the verifier, and the statement is simple. The prover wants to prove that they know a secret key corresponding to some public key. Okay? So this is a zero-knowledge proof.
To obtain a signature, the standard framework, for example, for Schnorr signatures is that one would compile this protocol into a signature scheme using the Fiat-Shamir transform. That's a very popular transform to get from interactive to non-interactive zero-knowledge proofs.
Okay, so what is Dilithium? Dilithium is basically following this framework, but the secret key and the public key relation is related to lattices. One simple example—the secret key could be a good basis, and the public key could be a bad basis. The prover wants to prove that they have a good basis corresponding to that lattice.
“We do not have any, say, mathematical proof that they will be secure against quantum computers, so there could be an unfortunate event that someday we wake up, and someone actually provides a quantum algorithm to break the lattice problems.”
So, so that's very briefly the Dilithium scheme. For Falcon, the Falcon follows the hash and sign methodology. Roughly speaking, the secret key will be a good basis for the lattice, and the public key will be the bad basis. To sign a message M, what you would do is that you would hash the message, and the hash would then be the target for which you want to find the closest lattice point. Then that lattice point is your signature.
Already from the description of both Dilithium and Falcon, you could see that they follow two different methodologies. [It’s] pretty common —I mean, these frameworks were developed way before these lattice schemes were defined in the previous setting, such as RSA setting or discrete logarithm.
So, how do they differ? Well, there are two—in terms of signature sizes, Falcon is very competitive, right? Like, 600 bytes. But then, the main strength of Dilithium is in implementation; because one thing is efficiency, and another thing is usability.
Another advantage of Dilithium is [that] the Dilithium shows more promise regarding extending signatures in the threshold setting. When we have multiple parties who want to sign the message. Basically there are different aspects: efficiency, usability, and also how you want to use the signature. Picking Dilithium or Falcon, it all depends on your type of application, basically.
Alex:
Okay, so, as you may have guessed, one of the issues that we're interested to talk about is quantum computing and the threat that quantum computing can pose to these different security schemes and cryptographic algorithms.
So, how does that relate to Falcon and Dilithium? What's the prospectus here? Where do you see this developing? Do you have a strong opinion?
Khanh:
So I agree that we see more and more countries pushing for the post-quantum migration. A lot of funding coming into quantum research, and quantum computers are becoming more and more powerful. As for Dilithium and Falcon themselves, it's the security of these schemes; they rely on lattice assumptions which we believe, until now, they are hard against quantum computers.
So we do not have any, say, mathematical proof that they will be secure against quantum computers, so there could be an unfortunate event that someday we wake up, and someone actually provides a quantum algorithm to break the lattice problems.
“People are getting more and more interested in post-quantum cryptography. That's how we're getting more and more efficient schemes… Lattice-based zero-knowledge proofs can be very competitive compared to the other post-quantum alternative”
This is a very pessimistic view, but at least based on the last, say, 30 years of cryptanalysis, or the community being very close together and being very transparent. Yes, we will likely see more and more attacks on certain parameter regimes of lattice schemes, such as Dilithium and Falcon
But the only consequence of these attacks could be that possibly you need to bump up some parameters. For example, I don't believe that we would need to replace the scheme entirely. But potentially, like, if some certain attacks arise, and we would need to, like, maybe change the modulus a little bit, or increase some dimensions a tiny bit.
But you never know. It could also be the case that there is a quantum algorithm, or even a classical algorithm, which just breaks lattice problems.
Alex:
Okay, that's very interesting, actually. I never thought about that possibility that in the future, there could actually be a classical algorithm, somehow.
Khanh:
Yeah, yeah, it's not guaranteed, right? Yeah.
Alex:
A major part of your work has been about lattice-based ZK proofs and the related construction to those. So, can you explain to me, maybe digging a little bit into the technical aspect of it, how are lattices being used in ZK systems today, and how does your research intersect with that?
Khanh:
Right. So let's start from the aspect of visibility. I would say that, around 10 years ago, lattice-based zero-knowledge proofs for very simple statements would cost a few megabytes.
Here we are, say, 10 years later. We could prove certain statements, such as proving that you encrypted correctly with, say, 15, 16 kilobytes. So you could see the progress we've made in the last 10 years made lattice-based zero-knowledge proof from completely impractical to a very interesting, concretely efficient, well, and potentially useful in real life.
“We're getting there, and I'm very happy with the progress we've made so far. So I'm really looking forward to the applications that lattice-based ZK may bring.”
So, what is the reason? Well, I think the reason is [that] there was no significant barrier to get this progress. I would say that people are getting more and more interested in post-quantum cryptography. That's how we're getting more and more efficient schemes.
So from a theoretical or from research point of view, we can see that lattice-based zero-knowledge proofs can be very competitive compared to the other post-quantum alternative, which are hash-based zero-knowledge proofs.
Compared to the hash-based schemes, we can see that lattice-based ZKPs or SNARKs are not yet popular in practice. So I think certain startups and companies are looking into lattices, but overall in terms of popularity, we don't see lattices being as applied as the hash-based ZKPs.
Which is interesting; on the one hand, the main difference is in the underlying assumptions, right? So for hash functions, you want to rely on the fact that a hash function is, let's say, collision resistant.
The advantages we see with lattice-based cryptography is that they carry more algebraic properties compared to the hash-based. They have much more algebraic properties. You have homomorphic properties; the rule of thumb is that if you're given more algebraic properties, you should be able to construct much more efficient schemes, right? Because you're given more functionalities.
But the cost of it is that these functionalities can be used by an adversary to break the lattice problems, right? So here we have the trade-off.
I think that, okay, so to summarize, we have lattice-based zero-knowledge proofs which are getting (at least theoretically) more and more efficient. But from the industry point of view, they are still not being adopted. Well, yet, because it feels like the area is still somewhat very active and young, which means that, okay, so why would we develop something which could be improved 2 years later by a factor of 2.
But I think we're getting there, and I'm very happy with the progress we've made so far. So I'm really looking forward to the applications that lattice-based ZK may bring.
Alex:
Yeah, so that's kind of a great bridge to the next topic that I know you're interested in, and certainly we here at Quantum Canary are very interested in—privacy-preserving cryptography. That's one of the recurring themes of your research. And it's useful for everything from anonymous credentialing, to electronic voting, and making payments, and all sorts of related things that are good and that we want.
So, where do lattices seem the most promising in those domains, and what makes them appealing for privacy-heavy applications? Are they appealing or not appealing?
Khanh:
Okay, so what I want to start with is the application of fully homomorphic encryption. Okay, so what is fully homomorphic encryption? It is an encryption scheme where you could perform operations on the encrypted messages without ever decrypting them. Okay, so let me just give an example; you have two ciphertexts which encrypt two messages. An example would be that you can create a ciphertext for the product of two messages by just multiplying the ciphertext.
Fully homomorphic encryption is an extremely powerful tool for privacy enhancing technologies. The link between this—the FHE and lattices—is that the most efficient constructions do rely on lattices.
FHE is also one of the [larger] selling points of lattice-based cryptography, because it is essentially the only practical way to build FHE.
So say we have FHE, we have encryption, but then we want to prove that the computation we made was done correctly. In particular, you may want to prove that you encrypted correctly. If the encryption is based on lattices, then, it is natural to have a lattice-based zero-knowledge proof because the statement itself already lies in that area.
"I think it's more of a difference between post-quantum and quantum cryptography in general. We consider post-quantum cryptography, …but security holds against both classical and quantum adversaries."
So I'm very excited about how lattice-based zero-knowledge proofs and privacy-preserving applications could be used in real life. So, there [is] a lot of interest currently on privacy-enhancing technologies, but just to be a bit more concrete on digital identity, on the digital wallet—for example, the European Union digital wallet, age verification in many countries, including the UK, or mobile driving license.
In all these applications, you have to prove that you have certain attributes which allow you to access certain services. If we want to have efficient solutions, which are also quantum safe, then one of the very interesting options, and potentially feasible, is by looking at lattice-based cryptography.
So what I'm looking forward to in the upcoming years is to promote and hopefully make some impact on the organizations and governmental bodies to consider lattice-based cryptography for such privacy-preserving applications. The main reason is, as we discussed before, so the quantum safe, post-quantum security, but also in certain scenarios, if you want to combine your application together with, say, FHE or Falcon Dilithium, it is very natural to consider lattice-based zero-knowledge proofs and related privacy-preserving applications.
Alex:
That's exactly what I was interested to hear, and just a quick follow-up on that, for people who are developing actively today, and they're thinking about how to manage identity, credentials, confidentiality, and transactions; where do you think is the most valuable place for those people to focus their attention within this space? What is going to be big in the next 3 years or so that they should probably know about, in your opinion, if there is such a thing.
Khanh:
Right. So, when discussing credentials or confidential transactions, they are all part of a bigger crypto system which has multiple building blocks, and it would be nice to use lattices, for example, but what's the most important is security. What is very important is to understand, in terms of building blocks, [is] whether the whole crypto system is secure without ever instantiating the building blocks; this can come later.
For example, just to give an example, suppose I want to build a confidential transaction system, so okay, so say I will need a signature scheme, say I will need some zero-knowledge proof, I will need some encryption scheme, let's say. So these are the building blocks, and we are still at the point where we possibly don't need to instantiate that. We don't need to think, okay, should this be lattice-based, or should this be hash-based, should this be group-based, elliptic curve, and so on.
Only when the whole framework is somewhat defined, then we can see what kind of security we are interested in. Do we want quantum security or not? Do we want speed? Do we want the smallest sizes as possible? Are we very conservative? Based on these criteria, we could decide on which schemes are the most appropriate for this scenario.
So I think it really depends; I can't really pinpoint to where exactly, but my guess would be in the instantiation phase, and also understanding what the priorities are. What priorities we have, because I am not claiming that lattice-based schemes are better than the hash-based in all aspects. So there are actually some aspects of the hash-based schemes which outperformed the lattices.
For example, for snarks and zero-knowledge proofs, currently the hash-based proof systems have much faster verification time. So, for certain applications, especially in blockchain, potentially you would need very fast verify time, because otherwise it gets costly, so for certain applications, you may want to use hash-based compared to lattice-based, so it all really depends on the application, and what requirements and priorities you need.
Alex:
So, over the next few years of your research life, what do you anticipate that you will be working on within this field?
Khanh:
It is a very interesting question. I wish I knew the answer. Maybe the future me will tell me. But I think we are getting to the point of—what is currently trending is considering—okay, so we have certain types of lattice assumptions, which we believe are hard against both classical and quantum computers.
A natural question is, “how far can we push these assumptions?” How far can we modify these assumptions so that we believe that they are still secure, but these additional functionalities or additional hints, they allow us to build more efficient primitives.
I'm currently starting to work on this area, but what I'm interested in currently is, if we assume these slightly—my colleagues call it “funky assumptions.” —and we cryptanalyze it, and we think that they seem to be secure, then what kind of efficiency gains can we expect in terms of applications?
For example, if we consider certain types of lattice assumptions, then can we reduce the proof size of ZKPs, or SNARGs, to be comparable to, say, group-based, or elliptic curve based? I think pushing the limits of the assumptions to gain more efficiency or functionality is, I think, what will be a very interesting and active area in lattice cryptography in the next few years.
Alex:
So, just before we wrap up, a really general question. Is there anything about lattice cryptography, or transitioning from pre-quantum security to post-quantum security that you think people misunderstand the most? Like, what do you think is the most misunderstood topic within lattice cryptography?
Khanh:
Let me think; it's a very interesting question. I think one—I wouldn't really say it's misunderstood, but it's important for post-quantum cryptography that we rely on assumptions.
One thing that is not highlighted well enough, is [that] we rely on lattice assumptions, which we believe is hard against not just quantum, but also classical computers.
I think it's more of a difference between post-quantum and quantum cryptography in general. People believe that lattice-based cryptography is cryptography which can be only implemented using a quantum computer. We consider post-quantum cryptography, meaning that the scheme itself can be run on a classical computer, such as laptops and mobile phones, but security holds against both classical and quantum adversaries.
Maybe one more thing, but it's a little bit more technical. So, for say, for software engineers or industry, it feels like lattice-based cryptography is in some sense, basically linear algebra. Okay, so like, when you look at the schemes, say, Dilithium or Falcon, you see a lot of matrices, vectors, you multiply them, and so on.
One thing to still keep in mind is this flavor of geometry behind lattices. It's always vectors which are short or lattice points which are close to the target. So the shortness and being close, they are all related to geometry of lattices, which I think that some people kind of start forgetting about and only see matrices and vectors, but this geometry is a crucial component in understanding why previous quantum attacks don't apply here.
Alex:
A lot to digest here, but I would—I want to be respectful of your time, so Khanh, thank you so much for taking the time to meet with us, we got a lot of wonderful material. Is there somewhere on the internet that people can follow you if they want to keep up with your research?
Khanh:
Right, so I have an account on X. It's Khanh Crypto. I also have a website, I forgot the URL. Yeah, so I am on social media. I guess not as active as I want it to be, but I'm catching up. Yeah, but the best way to contact me is via email.
Alex:
Okay, wonderful. Thank you so much again for joining us here at Quantum Canary.
Khanh:
Thank you very much.
