Hi, this is Subarna Goswami, Associate Editor with Information Security Media Group. I have the pleasure of speaking with Divesh Agarwal, Principal Investigator at the Centre for Quantum Technologies at the National University of Singapore. We will be discussing about approaches of quantum-proof cryptography and the plans around having some set of standardization. Welcome, Divesh, to the ice in the discussion.
Thank you, Subarna. So, Divesh, as I understand, there's a lot of work going on in the quantum computing space. However, when I speak to practitioners, what concerns them is the impact it has on cryptography. As a result, researchers are building quantum-proof keys.
So, offered I know current symmetric cryptographic algorithms are considered to be relatively safe against quantum computing. So, does this mean we do not need changes in the quantum keys? What exactly does this mean? So, I mean, for symmetric-proof systems, it's much easier to handle quantum attacks.
So, the best quantum speed up against symmetric-proof systems is via this algorithm by Grover. And to circumvent this attack, these kind of attacks, you can just basically double the key sizes and then you can work around these attacks. So, for symmetric-proof systems, it's much easier, but the main challenge for close-point cryptography is to work with asymmetric-proof systems. So, their quantum algorithms have made much more progress in classical algorithms.
By asymmetric, I mean the encryption key and the decryption key are different. And by symmetric-proof system, basically, the encryption key and the decryption key are the same essentially. And that is secret and that's not known to the adversity. So, basically, there is an algorithm.
So, let's say there is a classical algorithm that runs in time 2 to the n for searching something. So, let's say there are n different entries and you have to search one of them. And you have to, in a classical algorithm, you have to look at each of them. So, there is a quantum algorithm that does something much more surprising.
It basically solves it in square root n times. So, for this improvement, if you want to get around this improvement, it means basically you want to protect your system even against an algorithm that does search in square root n times. So, what you can do in that case is to basically just double your key sizes. And then the same kind of security guarantee is still possible.
So, what challenges NCI source face when it comes to asymmetric keys? So, as I said, the research on quantum group cryptography typically focuses on asymmetric or public key cryptography basically. So, these are typically based on computational problems for which the quantum algorithms are significantly faster than the classical algorithm. This is the best known classical algorithm.
So, this means that basically as soon as we have large-scale quantum computers, most systems that are currently used in practice will be broken. So, to get around this problem, the research in the current time and quantum in post quantum cryptography focuses on trying to come up with public key cryptosystems based on other computational problems that are hard to break, even using these quantum algorithms. And to study their security, those are the best known attacks best known quantum algorithms for these problems. So, to try to improve these quantum algorithms to try to study how hard these problems are with respect to quantum algorithms.
So, some such cryptosystems that are currently being studied are lattice based cryptosystems, these code based cryptosystems, multivariate cryptosystems and hash based cryptosystems. These are just names basically of cryptosystems that are based on some mathematical problems which are hard to solve, even using quantum computers. So, I did a bit of my research on quantum cryptography. So, I understand that a lot of research on quantum cryptography is currently focused on different approaches.
So, when you say different approaches, what do they mean by different approaches and what are these? So, as I said, the different approaches are based on different computational problems. So, these are cryptosystems that are not really comparable. So, you cannot really say that this one is definitely better than the other, because they are based on different computational problems.
To attack them, you have to come up with different algorithms and one algorithm for solving a problem will not work for solving another kind of cryptosystems. So, in that sense, these are not really comparable approaches, but the different approaches are lattice based cryptography, code based cryptography, multivariate cryptography, hash based cryptography. There is like a lot of these different cryptosystems. I mean, the essential idea is you have to come up with a computational problem that you can base public cryptosystem on and for which we don't know how to solve these problems using quantum algorithms.
So, the most standard cryptosystem that is currently used in practice, which is RSA, is based on the problem of factoring integers and this problem can be solved easily using quantum algorithms. So, the main goal is to come up with problems that are hard to solve. Okay. So, which is the most common approach right now?
You had mentioned you have mentioned lattice based cryptography. So, the most common, I mean, again, this is a question that for which the answer would be dependent on who you asked. But I think the most common is lattice based cryptography. I mean, it's the most well-studied.
It's the most sound in the sense that there are reasonably strong, provable guarantees that show that these cryptosystems are actually hard to pick. Lattice based would be my answer. So, the issue said that lattice based cryptography is currently one of the most common used. So, what is the reason behind that and if you could throw some light?
Sure. So, I mean, see, with public cryptography, the main thing is that we don't know, I mean, there is no provable guarantee that a certain problem is hard. It is just the only guarantee that we have is that after so many years of research, no one has found an algorithm to solve the problems or to break these cryptosystems. So, for lattice based cryptography, we can say a little bit more than that.
So, the practitioners typically compare different cryptosystems on various metrics, such as their efficiency or the promise security based on the best known attacks. But what makes lattice based cryptosystems particularly attractive is a much more fundamental attribute that is unique to these cryptosystems. So, the main reason lattice based cryptosystems are considered more reliable is that they admit worst case to average case reductions. What this means is that if one can break the cryptographic scheme even with small probability, then one can solve any instance of a certain hard lattice problem.
So, this property is what makes lattice based cryptography so attractive. So, for example, in cryptosystems based on factoring, the assumption we want to make is that it is hard to factor numbers chosen from a certain distribution. But it's typically not clear how to choose this distribution. So, obviously, we do not want to use numbers with small factors, but perhaps there are other numbers that we need to avoid and one needs to study this in reasonable detail.
However, when one talks about lattice based cryptosystems, one doesn't even have to worry about such questions. These questions do not arise because the cryptosystems are based on the hardness of worst case problems. So, in relation to our previous discussion, you had mentioned about NIST planning to come out with a standardization process around quantum proof keys. So, can you give some details on the need, what is the need behind this and what is the progress that has been made so far?
So, the need is basically because people believe that quantum computers will be a reality in the near future. So, in 2016, NIST published a report stating that it is expected that progress in quantum technology will be capable of breaking RSA and other probability cryptosystems that we use currently. And they anticipated the year when this will be a reality will be 2030. So, they expected that there will be last year quantum computers by 2030 that will break all these probability cryptosystems that are currently used in practice.
So, as a result, they thought that if there is a need to standardize quantum secure cryptosystems, which people currently study, and to this end, they announced towards the end of 2016 a call for proposals for such primitives. So, if I remember correctly about 80 proposals were submitted and after like about a year and a half of scrutiny, they shortlisted 26 proposals for the second round. And these proposals are currently in the process of basically further scrutiny and the hope is to have about 3 or 4 proposals in about 3 to 4 years and to try to standardize these so that they can be used in practice with reasonable guarantee of security against quantum computers. Thank you, Divish for sharing your thoughts around different approaches to quantum cryptography.
You're very welcome. You've been listening to Divish Agarwal for Ice Engineering. This is Supana Goswami. Thank you for listening.