Camille Morhardt: [00:00:00] Hi, and welcome to this episode of What That Means: Post-Quantum Cryptography. Today I have with me Raphael Misoczki who is a cryptographer at Google. His main areas of expertise are post-quantum cryptography (and we’ll ask him what that is), privacy-preserving cryptography, conventional cryptography and their application to common security flows.
So Rafael contributes to international standardization efforts on cryptography. [00:00:30] He’s an expert member of the USA delegation for ISO IEC and the co editor of the ISO IEC. 1 4888-4 standard. We can maybe get into that a little bit, too. And co-author of two submissions to the NIST–NIST is the national Institute of standards and technology That’s the American standards organization–the NIST standardization competition on post quantum cryptography. He got his PhD from the University of Paris in [00:01:00] France in 2013 and he also holds an MSC degree in Electrical Engineering and a BSC degree in Computer Science, both from University of San Paulo in Brazil, where he’s originally from. Welcome Rafael.
Rafael Misozcki: [00:01:15] Thank you very much for having me
Camille Morhardt: [00:01:18] It’s like long time no hear for you, because we actually met years ago when you explained what post-quantum cryptography was when you were working at Intel Labs. And I remembered how articulate that was. [00:01:30] And I wanted to talk with you again about it. So to kick us off, could you actually define post-quantum cryptography in under three minutes?
Rafael Misozcki: [00:01:39] Okay, so maybe I can start with what is cryptography first then I think to help us to get to the PQC post-quantum crypto definition. So essentially cryptography is the practice and study of a set of techniques that are used to achieve certain security properties and all of those in the presence of adversaries. So by properties here, I’m [00:02:00] talking for example about confidentiality, where we are interested to protect data. We want to let this data only accessible to some authorized users. This is achieved by using what we call encryption algorithms. And in very rough terms, these algorithms, they scramble the original data in a way that only owners of some secret key can revert such scrambling process and then recover the original message.
So one example of one algorithm that does [00:02:30] that is a AES, which is widely deployed. And other property that we are usually interested either in the world of cryptography is what we call data authentication, where we are interested to ensure that some data came from whoever claims to be the owner or the sender of this data. And for this purpose we use, for example, digital signatures, like RSA signatures and so on.
So the main thing here is that all this, uh, properties that I just described they [00:03:00] can be achieved as long as some very specific computational problems remain intractable. It’s impossible to solve those problems. Right. And what quantum computers bring to this discussion is that quantum computers can actually solve some of these problems much more efficiently than what classical computers can do. And as a result, we now will need to replace the cryptosystems that we use now by some schemes that you use, [00:03:30] um, computational problems that are intractable, even in the presence of quantum computers.
So this is the field of post-quantum crypto. It’s all about finding, detecting or creating new computational problems that can resist quantum attacks and then build crypto systems on top of that.
Camille Morhardt: [00:03:49] Very interesting. So you’re in the business of creating an intractable problem.
Rafael Misozcki: [00:03:55] Yeah, exactly. Well, most often we are, we’re reviewing the territory and [00:04:00] trying to find computational problems that do not seem to be amenable to quantum speedups. So quantum computers should not be able to speed up the solution of those algorithms, um, when compared to classical computers.
Camille Morhardt: [00:04:14] And I want to know all about that. So let’s dive a little deeper. So, can you please explain what is quantum compute? There’s quantum mechanics and there’s, you know, we’ve heard of sort of quantum physics, I think probably everybody’s heard of it right now. [00:04:30] What is that to begin with? And then how do we generate compute out of it?
Rafael Misozcki: [00:04:37] Yeah, that’s a very good question. So essentially quantum computing is a different computing paradigm. The simplest way to explain the difference between classical computing and quantum computing is how data is, uh, are represented. In classical computers we have bytes. And bytes can either star 0 or 1. There are just two states. [00:05:00] And in quantum computing, we work with what we call cubits and cubits they can start 0, 1 and also a superposition of the both states 0 and 1. So this property that I just mentioned, the superposition of states is exactly what allow amazing speedups to solve certain computational problems.
I’m not saying that this can be used to solve any problem. It’s just that this property can be used to solve very [00:05:30] specific computational problems. And as I mentioned, it happens that most of our cryptography date, it relies on computational problems that are affected by this quantum speedups
Camille Morhardt: [00:05:42] So pause for a second. Cause you mentioned super position and this is that notion. Uh, like you said, in classic computing, there’s, you’re either a 0 or 1. It’s either on it’s off in the byte in quantum. You’re saying actually until you measure it, it could be [00:06:00] both at the same time. And isn’t that fundamentally different than the physics of the universe that we learned about in the early 20th century?
Rafael Misozcki: [00:06:12] Uh, yeah, that’s a trick question. Um, in the end, we are dealing with quantum phenomena all the time, right? But there are several layers of interpretation of this phenomena. And my understanding is what the previous generation could see was only one layer above. And [00:06:30] now we are getting to this lower layer of understanding of the physics and how the word works actually.
Camille Morhardt: [00:06:37] Didn’t Einstein say something like I think that he was making the comment around quantum entanglement when he said it’s something like “scary magic that happens far away” or some kind of a quote like that, right?
Rafael Misozcki: [00:06:52] Yes. Yes. This is a specific property of quantum mechanics can offer. It’s not exactly [00:07:00] um, how can I say, related to the solution of the cryptographic problems we are talking here. We can use this phenomena of quantum entanglement to achieve something else, which is quantum key distribution. But I think this will go out of the scope of the topic here.
Camille Morhardt: [00:07:18] Okay, quantum key distribution. So, I’m gonna have you back on, and we’re going to talk about that because that’s very interesting also. So coming back to quantum compute, which is [00:07:30] essentially applying these quantum mechanics into a compute system, you’re saying you can have a super position which allows for a 0 or a 1 or a 0 and a 1 to exist. How does that make computing so much more efficient than it is classically?
Rafael Misozcki: [00:07:48] You can think about all the possibilities, for example, for every single byte of a piece of data, right? There are essentially two options. It’s either 0 or 1. And just, you can think [00:08:00] about your mapping, all these possibilities as a binary tree. Like every node, you have to go to 0 and then to 1. You have to make some verification, whether it’s 0 or 1. So you really go both branch of this three.
While if you are using a quantum computer, you are essentially visiting both nodes, 0 and 1 at the same time. And if you keep doing this for several layers, you start gaining what we call an exponential speed up because you are not [00:08:30] going at every layer you’re going like from one node, two, two, then four, then eight, then all powers of two.
And this provides like an exponential speed up. You can verify much more nodes than you would be able to using classical computing.
Camille Morhardt: [00:08:45] So you’re looking at, you’re not looking at this entire decision-making tree all at the same time. You’re still going layer-by-layer, but, but you’re able to look at all the options within each layer simultaneous.
Rafael Misozcki: [00:09:13] Exactly, exactly. That’s exactly the point. Yeah. Yeah. You turn something that would have like exponential time into something that’s linear time from that perspective. Yes.
Camille Morhardt: [00:09:24] OK. Well, let’s just kind of quickly go through this. Cause I think a lot of people might be familiar, but what [00:09:30] kinds of encryption is this going to affect? Is quantum compute going to realistically impact everyday people? Are we talking about obscure situations or are we talking about breaking the entire internet potentially?
Rafael Misozcki: [00:09:45] Yeah, it’s more the, the latter. So how essentially breaking, uh, most of the systems that, uh, has some security properties and I’ll tell you why. So essentially cryptography has two main approach which we call one [00:10:00] is symmetric cryptography. And in symmetric cryptography, the two communicating parts, they share the same secret, the same key. That’s how they can exchange secret message. And in the second approach is what we call asymmetric or public key cryptography. And in this public key cryptography, we have each party has its own private and public key. So each party has a pair of keys, right? And in practice, security protocols and systems, they use a [00:10:30] combination of both approach, together to achieve some security property.
So now what’s important here is that quantum computers are expected to break this two approach actually using different quantum algorithms. And the speed ups are also different. So for example, for symmetric cryptography, the expected speed up is important, but isn’t it won’t be enough to [00:11:00] completely break those schemes. It’s just a matter of increasing the parameters increasing key size, and you can still save your favorite symmetric crypto algorithm.
Now for public key cryptography, the expectation is that large quantum computers will completely break public key crypto. And by completely here, I mean that it’s not by just increasing key size or parameters that you can prevent attacks. No, the foundational [00:11:30] mathematical property there is broken in the presence of quantum computers. So that’s where it’s really the biggest problem. Here is public key cryptography, where we need to create new crypto systems to replace the existing ones. We cannot just increase parameters.
Camille Morhardt: [00:11:45] Where am I using public key cryptography? It’s my email and my online bank account.
Rafael Misozcki: [00:11:52] Yeah, it’s essentially everything. Public key cryptography is really widely used. For example, when you access a secure [00:12:00] website, when you have the lock, the https, the “s” means that you have a security layer and necessarily you’re using some public key cryptography to, to authenticate, at the very least, that you are talking with the website you expect you. And by breaking these things, if, to just be what we call it a crypto apocalypse (Camille laughs) because public key crypto is really is everywhere.
Camille Morhardt: [00:12:24] But you’re not suggesting that in order to provide an intractable problem [00:12:30] to a quantum computer, you need to be also using a quantum computer. You’re suggesting we can use classic computing, but we have to use a different kind of a paradigm of encryption.
Rafael Misozcki: [00:12:40] Exactly. Quantum computing will be very good to solve some very specific computational problems, but not all. The, the challenge here is, is okay. Let’s try to find some mathematical problems that are not affected by quantum computers. And if we find those, then we can just build new crypto systems that [00:13:00] can be deployed with classical computers, classical protocols and everything, and still be, uh, quantum secure.
So that’s the beauty. Post-quantum cryptography. We can deploy those right now, right away, because we don’t need quantum mechanics to actually deploy the solutions. Just need conventional computers.
Camille Morhardt: [00:13:20] So Raphael is that wishful thinking, because if you combine Artificial Intelligence with quantum computing, I mean, how long is it [00:13:30] realistically going to take a quantum computer to figure out whatever you put in place now?
Rafael Misozcki: [00:13:34] If we build a cryptosystem that’s considered secure by the crypto community, then we are talking about a computational problem that even if you live all the time of the universe and essentially all the atoms trying to solve this problem together with you, even though that would not be enough to solve this problem, just to give an intuition about how complex are those problems.
So even [00:14:00] using Artificial Intelligence, um, it’s not expected to, to really, uh, break those problems as long as they are well chosen and well, well defined.
Camille Morhardt: [00:14:09] So, so is the community who’s looking at this kind of a global community. Does that community agree on the solution or the framework for the solution? I know when I talked with you a few years ago, it was like, there was still some competing proposals. Yeah. Is that still the case? Or have we have we come [00:14:30] together as a globe?
Rafael Misozcki: [00:14:32] Yeah we have made some progress as of now industry academia and standardization bodies. They are all working together to define the next generation of cryptographic standards—in particular, post-quantum crypto standards. As of now, there are some standards which were already published. For example, NIST has published the document SP800-208, which defines a hash-based signatures, which is the same topic [00:15:00] of the ISO standard that I’m an editor that we mentioned in the beginning of the podcast.
So there are some standards which have been published since we talked last time, but the largest competition, which is also led by NIST, the NIST PQC competitions is still ongoing. And the truth is that there are various PQC approach–there are various ways of building post-quantum crypto systems and the community is still scrutinizing and understanding what are the most robust and [00:15:30] efficient approach among those. So there’s still some ongoing discussion and at least for the next two years or so, there should be some discussion about converging to one single approach.
Camille Morhardt: [00:15:44] So does the whole world use, uh, you’ve mentioned like AES or HTTPS, is that an example of something that’s converged and we’re going to do something similar? It might look different, but
Rafael Misozcki: [00:15:58] Yes. [00:16:00] AES is a cryptographic is an encryption algorithm that is a standard and is widely used worldwide in industry users and academia. But there are other algorithms that have been created that were created in other countries. And it’s just that they are not interoperable, but they might be just as good as AES. But in general, there is a desire, there is a wish to use the same algorithm because then we can make systems that can talk to [00:16:30] each other and it’s even easier for the community to actually check if a single scheme is secure or not rather than investigating a large set of schemes, given the complexity of the topic.
Camille Morhardt: [00:16:43] So if we’re moving from classic computer or we’re taking our, you’re calling them classic computers where that’s kind of funny, it reminds me of like Coke Classic or something. We’re still using the, what you’re considering a classic computer is like my most, my best, highest performance ever I’ve ever had. And you’re saying, “well, that’s [00:17:00] classic. That’s nice.” (Rafael laughs) But, um, what is going to be the impact for these classic systems are the most advanced systems we have today, as they transition to post-quantum cryptography? Will they be able to roll right into that? Or is there any kind of a concern?
Rafael Misozcki: [00:17:17] Yeah, that’s a very good question, too, because when we migrate to post-quantum crypto, very likely there’ll be a performance impact because most of these [00:17:30] new schemes, they are either less efficient or they require longer keys. So, this is exactly one of the main challenge. I think the current discussion is how to achieve post-quantum security and to achieve the same level of performance?
So this is a very hard, very hard question. Very hard problem. Uh, there have been some progress, but the issue, my, my intuition is that the system would still suffer from some [00:18:00] performance penalty while transitioning to PQC.
Camille Morhardt: [00:18:04] So, is this going to need to be like, if you’re saying that my email encryption and my bank online banking, encryption and everything, I sort of think of on the internet is going to have to transition on my regular computer. Is my laptop going to have to adopt this? or is all this stuff going to be done in the cloud where those applications are operating–or where the backend processing is operating?
Rafael Misozcki: [00:18:29] Yeah. [00:18:30] The short answer is that yes, your computer eventually will integrate this post-quantum crypto systems. And this will happen as follows. At first, we work on the PQC standards that will define the crypto algorithms. Then these crypto algorithms they will be adopted by higher level standards.
For example, protocol standards, like for example, TLS. Which is the security protocol for the internet. And then eventually, for example, your browser will [00:19:00] be compatible with this newer version of TLS. And therefore you have the crypto algorithm running in your machine.
So it starts in an adoption from the crypto algorithm to protocols, to systems and so on and so on. Usually this should be transparent to the user, except for what I mentioned. There might be some performance penalties. Hopefully in the coming years, we will be able to address this.
Camille Morhardt: [00:19:26] And what can system architects do now [00:19:30] to ensure a smoother transition?
Rafael Misozcki: [00:19:32] Oh, yes. So essentially one of the main problems, uh, we might face now is that some systems were built with very rigid structures. For example, the key size of the crypto systems could be hard-coded, which we mean, um, it’s hard coding the source code, so it might not be able to easily change the key size. So this kind of thing, they are problems [00:20:00] when you are changing the crypto algorithm. Right?
So one thing that systems architects and, and application developers could do now, Is to ensure that their application, their systems, they are ready to handle different crypto systems. If the key size changed, they would be okay. If the, the crypto algorithm change, they also would abstract this change. So this kind of things, this kind of practice is what we call crypto agility. [00:20:30] And crypto agility is really just a set of techniques that make systems more, um, easily updatable. And this is definitely something that architects now can do and no need to wait.
Camille Morhardt: [00:20:45] Are you talking about hardware systems? or software systems? or both?
Rafael Misozcki: [00:20:52] Essentially both. Uh, one thing to mention is that upgrading or changing hardware is usually harder. [00:21:00] Software is usually easier for us to patch. So it might make sense to, for example, looking to the hardware piece first, because they require maybe more time for this transition. But, uh, but in general, both would be affected.
Camille Morhardt: [00:21:15] So you’re saying like if you’re somebody whose company is designing cars or industrial machines or something that is likely to be around possibly still around and used in a decade or [00:21:30] so, you definitely at this point, it should be taking this into account?
Rafael Misozcki: [00:21:34] Yes, it’s a very good, very good direction to take now. Because on top of the complexity of making those changes in their system, there is also the process of changing out cryptography algorithms, which history has shown that takes long time. For example, elliptic curve cryptography is a very, very interesting crypto approach. And it was invented back in the 80s and it [00:22:00] took about 20 years to gain some adoption.
So the, the process of changing crypto algorithm,, this is something that takes a long time. So that’s why for example, this markets, this industries, and they should start looking into this transition as soon as possible, because it’s a long process. It’s a multi-year, uh, if not a decade-long process to change a crypto algorithm.
And one thing to mention is that actually, regardless of this timeline, there is also [00:22:30] another attack that actually is relevant, essentially, regardless of when quantum computers are built, large computers are built, which is the observation that some adversaries might be now harvesting encrypted data to break it later. That’s what we call store-now-break-it-later.
Camille Morhardt: [00:22:49] Oh! Store-now-break-later? That’s what she said? Wow!
Rafael Misozcki: [00:22:53] Yes. And, and just think about, for example, your social security number, right. Which is something that’s very [00:23:00] valuable now, but these will also be very valuable, like a few decades from now. And as such you’ve some adversary captured the encrypted format of your social security number and just wait until large quantum computers become a popular technology and then they will be able to break it right. And it still might be very harmful to, to users. So because of that, there is also, um, a desire to migrate to PQC as [00:23:30] soon as possible and prevent this kind of store-now-encrypt-later attack.
Camille Morhardt: [00:23:34] Wow. Something I wasn’t worried about until just now. Thank you for that. (laughs) So actually when are quantum computers arriving? Are there some real ones now? And are there, when do we expect them to be available more broadly?
Rafael Misozcki: [00:23:53] Yeah, this is a really hard question. To be honest, I’m definitely not qualified to give a precise answer [00:24:00] mainly because I don’t work actually building quantum computers, I work more on the security consequences of such a new computing paradigm. But what the community has been saying is about some potential timelines and the likelihood they turn out to be true. For example, professor ?Michael Mosca? from University of Waterloo, who is a very famous expert in this field, he says that there is a non-negligible chance that quantum company large enough, uh, to break [00:24:30] RSA could be built by the end of this decade, like by 2030 or so. And this is already very scary because such a risk should definitely motivate companies and organizations to just start planning and deploying it because it transition because if there is a non-negligible chance, well, there is a chance.
So, and this is a really big problem because if at some point we realized that there is such a large quantum computer Uh, as I said in the beginning, this would be a crypto [00:25:00] apocalypse because we cannot trust anymore our banking systems, our governments and information systems. The critical infrastructure systems which also rely on information systems. Uh, it would be a really big problem. So that’s why it’s important. You start preparing and deploying this transition sooner than later.
Camille Morhardt: [00:25:20] Okay. Yikes. And also very cool to be warned. Actually. Can you just give us, um, quickly, what are quantum [00:25:30] computers more adept at doing? Besides just breaking our encryption (laughs).
Rafael Misozcki: [00:25:36] One of them probably the best known is breaking cryptography, as of now. There are all other applications. For example, quantum physics simulation, which can be, uh, it’s expected that quantum researchers can [00:26:00] accelerate this problems using quantum computers. There’s also an expectation that by solving these problems–quantum physics and quantum chemistry simulation–they could be able to actually create a new drugs, new medications that, uh, as of now, we won’t be able to do it because we just, just don’t have this kind of computing power.
But again, as of now, it’s very limited, actually, the set of problems that quantum computers solve much faster [00:26:30] than, than classical computer.
Camille Morhardt: [00:26:32] Well, Raphael, thank you so much for joining today. I feel smarter and it’s just, it’s so interesting. It’s like, I go about my day and I don’t think about quantum physics and how it’s applied to compute. And obviously it’s a direct intersection with security because it’s encryption. So thank you so much for giving me and anyone who’s listening some insight into what this whole field is about and what it means and why it [00:27:00] matters.
Rafael Misozcki: [00:27:00] Thank you very much. It was a pleasure.
Camille Morhardt: [00:27:04] If you want to learn about homomorphic encryption, uh, there’s also an episode with Rosario Camarota and we have another episode on Cryptographic Services coming up with Eduardo Cabre. So thank you very much for listening.
