Quantum challenges to cryptography: why the future is already here

More and more often, we hear rather dramatic and movie-like statements about how the quantum era will change many aspects of our life, among which also cryptography and, therefore, security. It often feels like we are about to be thrown in a sci-fi movie in which we will live an extremely high-tech life, surrounded by super intelligent machines and ultra-powerful computers. At the same time, it feels like we have been at the edge of this “brave” new world for quite a bit of time, but never really in it; as if it was just a matter of time – even though  we cannot really say how long – before we have to change our perspective on things, get used to different capabilities and the consequences of new and unexpected technological developments. We are definitely starting to ask ourselves how close this future is and how disruptive the consequences of enhanced computational capabilities will be. The world of the future, this high-tech scenario, will of course be influenced and shaped not only by the quantum revolution: many other new and emerging technologies will also play a substantial role, from artificial intelligence to virtual reality. However, if or when quantum computers will become part of our everyday life, the way we do certain things will indeed change. For example, some of the ways in which we secure our communications and data – some of the currently used cryptographic methods – will be broken, putting at risk not just the security of the data of the future, but also the information we encrypt today and we want to remain secret for the next years.

In this episode, we will ask our experts in cryptography, Guglielmo Morgari and Edoardo Signorini, to discuss with us the issues faced by current cryptographic schemes with the advent of the quantum revolution. We will try to peek at the future of the security of communications and data. Actually, we will try to understand if, or rather why, that future is already here.

Edoardo, Guglielmo, thank you very much for joining us in this conversation today. It is past the time we wrap our heads around how new frontiers in quantum computing might affect current cryptographic methods and practices. Needless to say, the topic of quantum is spreading and a quantum revolution is definitely on its way in research labs around the world: from quantum physics to quantum computers to tv series to video games, the topic of “quantum” is often cited in an ever-increasing set of different scenarios, taking the perspective of a quantum era a lot closer to our everyday life.

After decades of heavy slog and little success, quantum computing is suddenly buzzing with increasing excitement and, complementary, with more and more worries. On the one side, quantum computers will open the door to a variety of fascinating applications: they may be useful to run complex virtual experiments, to model quantum systems or chemical reactions, to search huge amount of data, and to read secret messages communicated over the internet using the current technologies. Needless to say, the latter is a problem in many ways: voices are quickly raising saying that current encryption techniques will become useless once quantum computers will be out there in our world. At the same time, there still seems to be quite a bit of confusion among the general public regarding the extent to which current cryptographic methods will become useless, why that is the case, to what extent we should start worrying about it, and what the cryptographic community is doing about it. But before we start with the “heavy” stuff, we have a first very general question for you. In approaching the issues that quantum computers pose for cryptography and considering that we are definitely not experts in the field, where would you start from?

First of all, thank you for having us here. You are right: it is undoubtfully very important to discuss the issues raised by the development of quantum computers for currently used cryptographic techniques to shed some light on the extent to which current encryption will became useless, which algorithms will be broken, what scenarios will become problematic, and what the cryptographic research community is doing about these issues. And it is important to discuss these issues not just within the cryptographic scientific community. As it is for many other fields of research, being able to communicate outside your own inner circle in a way that is compatible and suitable for laypeople, is fundamental to build awareness and to get the correct message through.

So, where to start? To answer at least some of the most common questions about what happens at the intersection of quantum computers and cryptography, we might want to build the way up to the solutions that are being developed starting from the outline of where the problems come from. You might have already heard of quantum and post quantum cryptography: the two branches of cryptographic research that are actively trying to develop innovative solutions. The first builds on the principles of quantum physics and is moving towards solutions such as Quantum Key Distribution systems; the latter focuses on new mathematical solutions to define quantum-resistant cryptographic schemes. In order to understand the kind of solutions that the two branches offer, we ought to dive a little deeper into the problems they are out to solve.

That said, post-quantum and quantum cryptography are quite hard to explain without a little bit of background. One of the most complicated things when approaching quantum and post-quantum cryptography is that, in order to give even a schematic outline of the issues and theories, we need to deal with a variety of different notions and perspectives: from quantum mechanics all the way to quantum computers to quantum cryptography, the same principles and concepts give rise to very different applications and fields of research, definitely “entangled” but not equivalent. We will try to take you to the core of the problems first, and then to the different kinds of solutions.

For the sake of clarity, allow us one initial disclaimer: we mentioned the two main areas of research where people are currently working on possible answers to the problems we will be raising shortly.  As our goal here is to start from identifying the issues that current cryptographic schemes will face with the advent of quantum computers, and since this line of discussion will mostly lead us down a path focused on the mathematical aspects of cryptography, we will initially draw concepts mostly from the subfield of post-quantum cryptography. We are pointing this out here so that, throughout our discussion, we do not forget that the other branch, quantum cryptography, is as active and as important.

Thank you for this introduction. It is good to have a sense of direction, especially given how complicated and multifaceted the topic of quantum is. Coming from a non-technical background, we more than often have a hard time getting some things straight. Hence, before we dive into all the possible issues that cryptography will have to deal with, we wanted to ask you if you could give us a brief introduction on what quantum computers are. So, next question: where do quantum computers come from and what makes them so different from classical computers? 

Let’s start from the very beginning: to understand what a quantum computer is, it might be useful to briefly introduce the notion of quantum in the first place. Quantum mechanics, or quantum physics, is the science dealing with the behavior of matter and light at the submicroscopic level, hence on the atomic and subatomic scale, where the laws of classical mechanics do not allow us to describe the wacky behavior of photons, electrons and other particles. The behavior of these particles is very different from what we are used to experience and observe in our everyday life, making it hard to properly describe it with classical methods. For example, a first issue arises when we try to measure these physical entities. How can we do that? Here is where the notion of quantum comes handy. We can define a quantum as the minimum amount or unit of such a physical entity, the magnitude of which can take on only discrete values consisting of integer multiples of one quantum. Easy, right? Well, there is more.  A quantum is not something we can directly experience; hence, it becomes even more complicated to give a simple explanation of it. An example might help us. Think about light: the photon is the quantum of light and it determines the energy that can be carried by light as a function of its wavelength. As we will see, one of the interesting aspects of the quantum are its properties. We are not telling you this to bore you, but because having a general take on some of the core principles underlying quantum physics can be very helpful when we move on to more crypto-related issues later on, as for example what a qubit or Quantum Key Distribution are and how they work.

So, why are these theoretical notions of any interest to us? Because technology is now becoming better and better at skillfully manipulating quantum phenomena, leading the way to applications that have quite a magical taste, such as the quantum computer. Even though, in many ways, fully-developed quantum computers are still a matter of research and intense debates, the concept behind quantum computers was put forward already in the 80s, when Feynman and Deutsch, pioneers in the field of quantum physics, realized that, in order to study quantum phenomena, it would have been useful and advantageous to simulate them. Now think about this: in a classical computer, information is codified in bits. Each bit is a single piece of information that can exist in two states – either 1 or 0. Hence, information is stored and processed as a combination of 0s and 1s in a sequential way, essentially doing things one after the other. This principle underlying classical computing enables our machines to do amazing things and to be very fast, but they are still bounded to the structure of the bits. This becomes quite problematic when we want to simulate phenomena that respond to quite a different logic, such as quantum phenomena. Hence, the original idea was to come up with a more efficient way to simulate quantum phenomena, a way that could be closer to the logics of quantum physics and that essentially implicated to rethink the very principles underlying the processing of information. This, roughly speaking, was the offspring of the concept behind the quantum computer, which, however, remained just a concept for quite a while, mostly considered an exercise in style or regarded as some sort of mythical creature.

Sorry to interrupt you, but this last observation sounds rather interesting. How can there be so much fuss about something that was still recently considered as a mythical creature? How did we get where we are at now?

Well, on the one side, the quantum computer is still a mythical creature in the sense that we cannot go out and buy one, but, on the other side, quantum computer prototypes are definitely already here. We were saying before that the concept behind quantum computers rests on a different notion of information processing compared to the one implemented on classical computers – which, again, work with 0s and 1s. Not too long ago, starting from the principles of quantum physics, researchers developed what we could call a “new” bit: the quantum bit, or qubit. And here’s where the actual revolution is. The qubit is the basic unit of quantum information. Now, the difference with the classical bit is that quantum mechanics allows the qubit to be in a coherent superposition of state 1 and state 0 simultaneously: quantum properties are used to represent and structure data, and quantum mechanisms can be devised and built to perform operations with this data.

What does this mean in practice? If we ought to simplify a little, it means that computers using qubits can store way more information using less energy than classical computers. In principle, given that the qubit is not either in the 0 state or in the 1 state, but can assume infinitely many superposition of the two states, you could encode information of infinite length in it. This in principle. The problem is that a measurement or observation of a qubit would inevitably destroy its coherence and irrevocably disturb the superposition state. Nonetheless, it is clear that the concept behind information processing based on quantum physics is very different from the classical one and it allows to manage much more information at once. Instead of analyzing each unit of information sequentially, superposition in the qubits allows to process information in parallel. Therefore, for example, the time it takes to crunch data is significantly reduced.

This gives us a very general overview on what quantum computers are and on the principles on which they operate. Besides the interest for quantum computing and quantum computers from the technical point of view, the importance of quantum computers lies in what they can do and, consequently, in what they will allow us to do. There will be tasks in which quantum computers might not have a real advantage over classical computers and, hence, little will change; other tasks will become much faster; and other tasks that were impossible before will become possible thanks to quantum-enabled computations. Especially this last aspect, i.e. that quantum computers will turn some of the impossible problems possible, is what is raising a well-justified fuss.

Qubits that store great amount of information, greatly enhanced computational power that will open to new frontiers and applications, unsolvable problems that all of a sudden become solvable, seem to be some of the key features of the new quantum era. As you can imagine, this last aspect – unsolvable problems that become solvable – is extremely fascinating and triggers everyone’s imagination. What you often read in blogs or similar sources is that quantum computers will be able to solve problems that are impossible or would take a traditional computer an impractical amount of time – like several times the age of the entire universe – to solve. Well, besides the indisputable enchantment of unsolvable problems becoming solvable, we would like to dive a little deeper in what this means and what the practical consequences would be in our everyday life. But before we go down that road, we still have an open question about the state of the art of quantum computers.

If we are getting it right, quantum computers, or at least quantum computers that can solve currently unsolvable problems, are yet to come. Can you tell us something about where we are at now in terms of actually producing a quantum computer? Provocatively, when will we be able to buy one?

This might not be an easy question to answer, because the answer depends on how exactly we pose the question and, if we ought to summarize a very general answer, much is still a matter of time, in many different ways. It depends on what we mean when we ask if quantum computers are already here: if, for example, we are referring to a possible quantum advantage or to the quantum supremacy. It also depends on whether we are referring to full-fledged, almost off-the-shelf quantum computers, which are definitely not here yet, or to prototypes that are much more than simple toys, and that are definitely already here.

On the one side, technologically advanced governments, like the United States or China, are considerably investing in quantum computers as they would give them substantial technological advantage. On the other side, Google, IBM and a handful of startups are racing to create the next generation of supercomputers and interesting results are already on the way. Big players in the ICT industry, like D-Wave, Google, IBM, Microsoft, all have their prototype of quantum computer. We are definitely witnessing a rapid acceleration in both research and delivered results. For example, IBM has made available online to everyone a quantum simulator by means of which it is possible to test quantum algorithms on your computer and it is also possible to run those algorithms in cloud on an IBM quantum computer to check and verify the results. There are also firms providing other interesting services related to quantum computing: for example, Atos provides simulators of different versions of quantum computers based on different physical models. You can use these simulators of quantum computers to compare how software and algorithms behave and perform on different models. Needless to say, all this is already incredible.  So, in a first way, it is most probably just a matter of time before we develop an even more advanced version of a quantum computer.

On the other side, the question of whether we already entered the quantum era or not depends on how we describe the quantum era in the first place. Two common definitions are: we will reach quantum advantage when a quantum device will solve a problem faster that a classical computer. And this is one thing. Another thing is quantum supremacy: the goal of demonstrating that a quantum device is able to solve a problem that classical computers are not able to solve. There are many debates about this distinction and about where research is positioned at the moment. Anyway, what are these problems that classical computers cannot solve? What does it mean for classical computers not to solve a given problem?  What we can say at a very general level is that if we gave enough time to a classical computer it could actually solve any problem for which a solution algorithm is known. The issue arises when the time we ought to give to a classical computer is of hundreds of thousands of years or more. Definitely out of the human time scale. This is, roughly speaking, what an “unsolvable” problem is in this context: a problem for which there is yet no algorithm that can solve it in a reasonable and useful time. So, if we simplify a little, quantum computers will – thanks to greatly enhanced computational power – reduce the time it takes to solve certain problems – the quantum advantage – and, in some cases, will decrease the time it takes by so much that unsolvable problems will become solvable – the quantum supremacy. In technical terms, quantum computers might decrease the time it takes to solve hard mathematical problems from non-polynomial to polynomial, making unsolvable problems solvable. Among these hard problems, but we will get to it later, there are also those hard problems on which some of the current cryptographic schemes are based.

Allow us just one quick note on this. As for now, it does not seem we are yet at the stage of having reached the quantum supremacy milestone. There was a recent quarrel between Google and IBM on this. In 2019, Google published a paper on Nature in which they demonstrated that their quantum processor was able to solve a very difficult problem – it was able to recognize certain statistical regularities in random sequences – in something like 200 seconds, whereas they claimed that the same calculation would have taken IBM’s Summit, the world most powerful supercomputer, 10.000 years. IBM pushed back on the claim saying that its machine could solve the problem in 2.5 days, hence setting a much higher threshold for quantum supremacy.

Alright, we see what you mean by saying that it is a matter of time in many different ways. We cannot yet buy a quantum computer, but it might just be a matter of time. Similarly, it could be a matter of time before we reach quantum supremacy. On the other side, quantum computers reduce the time it takes to solve certain problems making them solvable. And even if there are not here yet, it might be a matter of time before quantum computers become powerful enough to actually solve these problems. Well, you made the point very clear: it is not just about whether quantum computers already exist or not – the answer might not be a clear yes or no – but it is about what quantum computers can, cannot, or will be able to do on various levels in various possible applications, one of which is cryptography.

Yes, it is quite right. Allow us to add just a few observations: in the first place, if and when powerful enough quantum computers will be available, just some cryptographic schemes will be broken, and specifically those which are based on mathematical problems that are computationally hard and for which no efficient solution algorithm on classical computing systems is publicly known today. In the second place, a quantum computer is not just a computer that goes faster, even if – in general – we could say that quantum computers will be faster at solving certain tasks, but a computer that does things radically differently, building on the laws of quantum physics. Now think about this, and we will try to explain it better later: quantum algorithms that could in principle break current cryptographic schemes have been around for over 30 years now but, if you try to run them – with all required adjustments – on a classical computer, they would not really benefit you at all. On the contrary, these algorithms ran on quantum computers will be extremely effective and, with quantum computers becoming progressively less of a mythical creature, the search for cryptographic schemes that could resist quantum attacks has become almost a priority in the cryptographic community, especially after the NSA, in 2015, publicly announced that the time had come to start developing quantum-resistant schemes.

Thank you so much for your comments on this. We should now have a general understanding of what quantum computers are, what they will be able to do, and where research is at right now.

Let’s turn to cryptography now. We have already touched on some of the issues in our conversation so far, but it is time we crack the books and dive into what happens at the intersection of quantum computers and cryptography. First things first, some concepts you mentioned are not so intuitive if you are not of the field: for example, we have briefly encountered the notion of hard problem earlier in our discussion, but it is not clear to us yet how they relate to cryptography in the first place. And maybe even before that, what do you mean when you say that only some cryptographic schemes will be broken? What kind of cryptographic schemes will resist and what will be broken? Intuitively, drawing from what you told us before, it seems that cryptographic methods based on hard mathematical problems – those “unsolvable” problems that will become solvable with quantum computers – are the ones that will be broken. Can you start from this to give us a better idea of how the intersection between quantum computers and cryptography plays out?

It’s definitely a good idea to recall some basic distinctions among currently used cryptographic schemes before moving to if they will be broken when powerful enough quantum computers will be available. We will try to keep it simple, and maybe the easiest way to approach the distinction we are here interested in – that between symmetric and asymmetric cryptography – is by means of a quite effective metaphor: that of mail boxes.

Both symmetric and asymmetric cryptography allow us to communicate with another person in a secure way: if our encrypted message is intercepted, it cannot be read by an attacker or, more generally, an unauthorized third person. So, both schemes have the same goal but carry it out in different ways and are grounded on different mathematical solutions. Symmetric cryptography works more or less like this: imagine we both have the key to a lock and I want to send you a secret letter. What I will do is to simply put the letter in the mail box which is locked with our lock and we will both be able to open the box and read the letter. This translates quite straightforwardly in classic cryptography using a symmetric key, where the same key – the secret that is shared between the parties – is used for both encryption and decryption. This method is very efficient but it has one main problem: how do we exchange the key in a safe way? Even intuitively, if we both have the key to open a certain lock, we have had to exchange it in a way that is itself secure. This fact highly limits the possible application of symmetric cryptography. For example, if we had to meet somewhere to exchange the key, we can easily see how that would be impossible if you wanted to exchange a key to establish a secure communication to buy something online from an Australian vendor. In such case, we clearly want the information we share during the communication with the vendor to be secure, our credit card number for instance, but it is likely that we did not have the chance to exchange the secret key before. How can we solve the problem of exchanging the key in a secure way?

Public-key cryptography, also called asymmetric cryptography, allows us to exchange the secret key in a secure way. In principle, asymmetric cryptographic schemes would also work by themselves as a method to secure our communication; but, as they are generally slower than symmetric schemes, what we usually do is that we exchange the key by means of asymmetric schemes and then we use that key to communicate using symmetric encryption.

Here is how asymmetric cryptography works at a very general level: in asymmetric schemes, that were invented around the 70s, the receiver has two keys, a private and a public one. One of the main differences with symmetric schemes is that in public-key cryptography, the key that is used to encrypt is different from the one that is used to decrypt. Let us try to make it a little clearer with an example: I have a public and a private key; the public key is, of course, public, in the sense that whoever wants to send me a message can do it by using that key to encrypt it; but I am the only one who can decrypt those messages because I am the only one who has the private key corresponding to that public key. So, the public key is my mail box; whoever wants to send me a message can put it in my mail box; but I am the only one who can open it, because I am the only one who has the key. The mail box is the public key because I tell everyone who wants to send me a message to put it in there. The key to open the mail box and take the messages out is the private key, since I am the only one who has it.

Hence, as we were mentioning before, we can use this scheme to exchange the secret key, and then we can turn to symmetric encryption. We could simplify this concept by saying that we first share the key in a secure way by means of asymmetric cryptography; someone goes to your mail box and puts a key in it. A key of which he or she has a copy. Of course, we have also to make sure, in a nutshell, that the right person is putting the right key in the right mail box, so that we do not end up giving our secret key to the wrong person. Very broadly speaking, this is what authentication methods are for. Well, at this point, when I then go there and take the key out of the mail box, we can start communicating in a secure way using symmetric encryption.

Just a brief clarification: the metaphor of the mail box covers just one possible way in which we exchange the key – for instance, the one on which RSA is based. Other asymmetric cryptographic schemes use slightly different methods. Although just a partial explanation, the metaphor we introduced you to is nonetheless a good starting point to get somewhat comfortable with the principles behind asymmetric cryptography.

Now, back to the point, can you guess which one of the two kinds of cryptographic schemes will be broken by quantum computers?

Well, actually we know an answer – but just in a very dogmatic way – in the sense that it is known that asymmetric cryptography is the one that will be broken. And what we mean when we say we know it in a very dogmatic way is that we have no idea why that would be the case. But, if we ought to make an educated guess, it might be here that hard mathematical problems come into play.

Correct, the answer is in the math. The math behind symmetric and asymmetric cryptography is quite different. Public-key cryptography is based on those computationally hard problems we were talking about before. We just skimmed over the notion, so let us go a little deeper into the definition. But we will first narrow our scope down to those computationally hard problems that are of interest for asymmetric cryptography. There are many other kinds of computationally hard problems, but discussing them all would take us far beyond our scope.

The kind of hard problems on which asymmetric cryptography is based are those for which is very hard to find a solution, but for which it is easy to verify that a certain solution is correct. Now, if you think about it, this is also how asymmetric cryptography works: it is easy to do an operation in one direction (putting the letter in the mail box, verifying a given solution, encrypting a message), but it is hard to do it in the other direction (opening the mail box, finding a solution, decrypting a message). Asymmetric cryptography is based on this logic: i.e. on the assumption that the integer-factorization problem and the discrete-logarithm problem are hard to solve. As for the first, the integer-factorization problem, if I give you two numbers and ask you to multiply them – let’s say, 521*547 – you might have to use pen and paper, but you will be able to come up with the solution rather quickly – 284.987. But if I give you a number –let’s say 746.789 – and I ask you to tell me which numbers, when multiplied, give you that precise result, you will see that that calculation is not as easy as the first. And the same applies to computers operating on very large numbers: if you give a computer a number larger than 1024 bits, the computer is not able to factorize it, or at least it is not able to do it in a reasonable amount of time. This problem is at the basis of the RSA scheme. Similarly, the discrete-logarithm problem, another problem that is easy to solve in one direction and difficult in the other, is at the basis of elliptic curve cryptography and of the Diffie-Hellman for key exchange.

The security of these cryptographic schemes is based on the assumption that the mathematical problems underlying them are hard to solve. But again, a hard problem of this kind is difficult not in the sense that it is by no means solvable – think about factorization, if you try all values up to the square root of your number you will eventually find the right ones; it is difficult in the sense that, for now, even if you had an algorithm that could solve them, it would take so long to find the solution that it would be out of scale with your needs. Technically speaking, the time to solve these problems is not-polynomial with regard to the size of the input. If you are an attacker and you want to break RSA with conventional existing algorithms, it would take you thousands of billions of years to actually break it. You can easily see how this kind of attack will essentially lead to nothing.  The assumption according to which the integer-factorization and discrete-logarithm are hard to solve has proven to be reliable over recent decades, in case traditional computing systems are used.

But now that quantum computers are, or at least it is possible they are, on their way, things are likely to change. You are just about to ask us why. Well, quantum algorithms that could potentially break asymmetric encryption schemes have been around for over 30 years now. As it was – it is – not possible to run them on quantum computers, they remained marginalized and underrated. But now that we might be closer to quantum computers than we think, these algorithms are indeed becoming a problem.  Especially Schor’s algorithm, once quantum computers will be large enough, will break currently used asymmetric cryptographic schemes as it will reduce the time it takes to solve both the integer-factorization and the discrete-logarithm problem from non-polynomial to polynomial, from hard to easy. The result is that cryptographic schemes based on these once-hard problems will be structurally broken and the exchanged key will be just useless. For symmetric cryptography, the situation is slightly different as Grover’s algorithm for quantum computers reduces the equivalent security of the algorithm to half of the length of the key. An algorithm that has a key on 128 bits is expected to have a complexity of attack of 2¹²⁸. With Grover’s algorithm on a quantum computer its complexity is expected be reduced to 2⁶⁴. From a cryptographic point of view, this is in principle devastating, as it means to have a security that is reduced from 128 bits to 64 bits, which makes the attackmore than a trillion time faster than before. As dramatic as it might sound, the solution is easy: we just double to original key, from 128 to 256 bits. And we are already implementing and adopting symmetric schemes with keys of 256 bits, so we will be good on that side. The real issue is with asymmetric cryptography.

So, you are basically telling us that asymmetric cryptographic schemes based on these hard problems will become breakable once quantum computers will be large enough to implement quantum algorithms, such as Schor’s algorithm, as it will dramatically reduce the time it takes to solve such problems. But, at the current state of the art, asymmetric cryptography is secure in the sense that, at the moment and as long as quantum computers are what they are now, encryption schemes based on such problems can still keep our information and communication secure.

This is not exactly how you should think about it. Well, you are not inherently wrong, but there are some more considerations to make in order to have a more realistic view of the actual threats and the extent of the possible threats that would follow the implementation of larger quantum computers.

First of all, when dealing with security issues, on the one side, it is of course important to think about the issues of today; but, on the other side, it is even more important, and extremely more complicated, to think about the possible issues of tomorrow and to build the right security frameworks to always be ahead of time. If you wait for a threat to be in place before thinking about how to protect yourself from it, it is highly likely that you will not have the right solution at the right time. The time to build a dam is not when the flood wave is arriving. Ideally, we should be able to read the threat of a flood wave well in advance so to allow the time to build the dam and hence to prevent the catastrophic effects of a massive flood. And this is true for almost all issues related to threats: one of the most difficult jobs in security is to come up with ways of dealing with the unknown and the unexpected. But it becomes even more important when research in a given field takes time to come up with well-defined, and especially broadly accepted, results. Research in cryptography takes time: it takes time to develop and standardize quantum resistant asymmetric cryptographic schemes; it takes time for cryptoanalysis to corroborate possible solutions; it takes time for a certain quantum-resistant solution to be broadly implemented. When you have to build a dam to prevent a flood, you might have to study the landscape and adjust the construction of the dam accordingly. Well, in the case of cryptography, it is more like if you had a river that eventually will flood and you cannot simply build a dam: you must come up with a totally different way of containing the flood.  So, as the level of water in the river increases – research in quantum computers is moving quickly – you should come up with a solution – quantum and post-quantum cryptography – well before the flood happens, to have the time to implement it and save your village from being wiped out. So, out of metaphor, we have to think that, in order to be ready by the time full-fledged quantum computers will be around and asymmetric schemes will be broken, we have to research solutions well ahead. As we were mentioning at the beginning, quantum and post-quantum cryptography are actively working towards possible solutions.

Especially research in post-quantum cryptography was recently boosted by an initiative of the National Institute of Standards and Technologies. We already mentioned it: in 2015, the NSA publicly announced that it was time to start thinking about quantum-resistant asymmetric schemes. In 2017, the NIST launched a call for proposals to develop and standardize post-quantum cryptographic schemes. We are now at the second round of this call, and it is unlikely that the NIST would close it within three years. Hence, the standardization of post-quantum cryptography might take longer than it might take quantum computers to be fully developed. Let’s suppose that quantum computers able to break current asymmetric encryption schemes will be ready in 10 years from now; well, it might take us longer than that to have a cryptographic solution that is – so to say – up and running by that time.

Why is this important? Why do we necessarily have to be ahead of time, especially when it comes to developing cryptographic methods that will resist quantum attacks? Well, on the one side, as we already said, it takes time to do research and to come up with a reliable solution; and it also takes time to broadly apply that solution. On the other side, besides being an active and fascinating field of research, cryptography is a very practical matter with applications that are different in different scenarios. So, if you think about your private communications, as your private text messages, then in that case, you do not really need to worry about quantum computers and quantum attacks yet. But there are sensible data about individuals – let’s say, information about your genetic code – that will still be the same in 30 years and, as we will still be alive, will still be sensitive information that need to remain protected. As that information is for now encrypted with asymmetric cryptography, an attacker who will have a quantum computer, in 10, 20 or even 30 years, will be able to access that information. Now, you might argue that it is unlikely that quantum computer will become widespread enough to be a problem for individuals and their data. That is arguable as there is for sure someone out there that is recording data and that one day may be interested in decrypting them. But even if it turns out you are right and no one would use quantum computers for these kinds of attacks, there are scenarios in which quantum attacks will be extremely likely: for instance, quantum computers may be used by state actors, or state-affiliated groups, to find out information about another countries. Think about national secrets that need to remain unintelligible for the next 10 years to say the least. Well, if we do not come up with reliable solutions soon – post-quantum cryptographic schemes that will resist quantum attacks – information that are encrypted using today’s schemes may become readable in the near future. Ideally, we should be ready to implement quantum-resistant cryptography, quantum and post-quantum solutions, well before quantum computers become an actual threat to information and communication. Chances are we might already be late. We might even push our considerations a little bit further: actually, all the information that has ever been encrypted using asymmetric cryptography will eventually be exposed once quantum computers will be able to solve those unsolvable problem on which asymmetric cryptography is based. This is even more problematic than the scenarios we were discussing before, as we cannot really do much about the information that has already been encrypted. However, what we can do is to focus on finding and implementing quantum-resistant solutions to secure information that is yet to be protected.  To conclude, as far as cryptography is concerned, it is not really a question about when we will enter the quantum era  – in the sense that full-fledged quantum computers will be available and we will meet the quantum supremacy milestone – but rather a matter of being ready to properly face quantum attacks considerably before the quantum era actually begins, so to protect both the data that we will generated from that time on as well as the data that we encrypt today and for which protection needs to be guaranteed over the years or decades.

Well, this definitely changes our perspective on things in a way we never thought of before. On the one side, as it is often argued, “the net never forgets”: the data that we are producing, sending over the internet, and that is stored somewhere, may become available and be disclosed well beyond what we are generally used to think of. Not even to mention those segments of our society for which protection of data over extended periods of time is crucial and a matter of national security. But, as you were explaining us, the delicate aspect is that the longer we wait to reshape our protections against quantum attacks, the more likely it is that our data will be eventually exposed. It is not an easy concept to summarize, but it seems like that, when it comes to understanding the challenges that the quantum era poses to cryptography, the future is actually already here: the solutions that will protect our data once quantum computers will be available are the quest of today. We should not wait for current cryptographic schemes to be broken to feel the urge to find a remedy. Quantum and post-quantum cryptographic solutions need to be in place before the quantum era actually begins. In the words of Catherine Bessant, chief operation and technology officer at Bank of America, “The risk of today is interesting, the risk of tomorrow is what is most important”.

Once more, we want to thank Guglielmo and Edoardo for the enlightening conversation and the precious comments on the challenges that cryptography is facing with the advent of the quantum revolution. But that is not all. In the upcoming episodes we will ask our experts about new methods in quantum and post-quantum cryptography, diving deeper into how research is shaping the present and the future of data and communication protection.

For more related articles, check our blog.