Below are the keynote remarks by Dr. Aaron VanDevender at the Hudson Institute event tiled The Coming Quantum Revolution: Security and Policy Implications.
All right. Thank you very much, Arthur. It’s a very, very, warm welcome. I’m very privileged to be speaking to you this morning.
Let’s see – are my slides available? Great. Here we go. So, I’d like to be talking about secrets, magic and quantum computing – sort of three of the big resources that we use to drive a lot of the value in our society.
So, the first time that I heard about quantum computing – the idea of quantum computing is 20-plus years ago. And it really struck me as the closest thing that we could come to, to a science-fiction-like technology to be made real. And when I think about science fiction, more than being just about the future or being about space or it being about science as research; it’s really about how big ideas can impact and transform society – impact civilization.
And so, quantum computing is one of the few things that really has that ability to have a large-scale impact on civilization. And so, if we’re going to be thinking about quantum computing in science fiction sort of terms I’d like to get a quote from Arthur C. Clarke, one of the great science fiction authors who had three laws, the third of which is the most well-known: any sufficiently advanced technology is indistinguishable from magic.
Which provides great insight on what it must be like to say the medieval person exposed to iPhones and 21st-century technology and have no way to distinguish that from magic must seem pretty amazing. But actually, I’m going to say that this is wrong – that there is something very important that distinguishes magic and technology that Arthur C. Clarke missed.
And to demonstrate that, first let’s talk about a couple of examples of what we agree on is magic. So, Luke Skywalker, the Star Wars universe, uses the Force which is very clearly a magical power. In this example he’s trying to raise his X-wing fighter out of the swamp under the tutelage of Yoda and his ability in order to accomplish this feat is strongly correlated to his belief in the Force; in that he uses the power of belief to conduct this action.
We also have the elf coming down from the North Pole trying to save Christmas. Santa has this sleigh that has this jet engine but instead of being powered by kerosene or rocket fuel, it’s powered by the belief in the Christmas spirit. And so, the elf’s job is to make sure that enough New Yorkers believe in the Christmas spirit to power Santa’s sleigh, so he can deliver all the presents.
And then the best example of magic that I always come back to is that, of course, of Tinkerbell who can only fly if enough people believe in fairies. So, who here believes in fairies? Everyone clap if you believe in fairies. Okay. Great. Great. So, the belief in fairies and expressing that through clapping drives the pixie dust to have this to give her this magical ability.
And so, the thing that we see that distinguishes magic from technology is that it is powered by a belief -- you need core beliefs in order to make the magic work and something that’s not true for real technology.
So, cryptography one of the basic technologies or tools that we have in our society, though, by this definition is actually magic. It is not pure technology -- that it requires belief in order for it to perform the function that we use from it.
So, RSA public-key cryptography was invented by Rivest, Shamir, Adelman in 1977 at MIT – and they were playing with one-way functions from number theory using prime numbers to create functions where you could separate the encryption key from the decryption key and realize that this sort of scheme had lots of really great benefits for sharing secrets.
So, they got real excited about it – patented it and then after fooling with it realized that it had many other benefits including not just sharing secrets but also digital signatures and creating trust networks and all these other things.
But that the core driving piece of it is that it’s based on an unproven mathematical conjecture that large numbers are hard to factor into their primes. And there’s no proof for this but everyone believes it to be true, but that’s sort of the essential element; is that this belief that it is a difficult thing. And if for some reason we were to stop believing that then all the tangible benefits that we derive from RSA public-key cryptography would vaporize.
So, you can think of cryptography as a sort of machine that takes in the belief of the difficulty of this problem and turns it into security – it turns it into trust, turns it into authentic transactions and relationships and the things that we derive tangible benefits from.
But if something comes along that were to dispel that belief then the whole edifice of public-key cryptography would crumble. The math would still work – all of our computers would still be performing those calculations but all of the tangible benefits that we derive from it would suddenly evaporate because if you can’t trust the system—if you can’t believe that large numbers are hard to factor, that these problems are computationally unsolvable then we would no longer be able to invest those resources into building up that infrastructure.
Which if you think about it is a kind of crazy paradigm to have a technology that works and works very well, and we get lots of benefits from it and then a new technology comes out that not just obsoletes it but makes the old technology stop working.
It would be sort of like Thomas Edison invents a lightbulb, works for 100 years, lights up our homes and then one day someone invents an LED light bulb and you walk into a room and you flip a light switch and it doesn’t work anymore. And the reason it’s not working is because we just stopped believing in light bulbs now that LEDs exist.
Fortunately, light bulbs are not magic., Tthey are just technology, so we don’t have to worry about them stopping working just because something better comes along. But that is the risk when you build things based on magic and not based on pure technology.
So, the magic that we have, however, provides us lots of really great benefits. It was primarily designed to drive secret sharing as cryptography systems are used going back to Caesar, using rotational codes to communicate with his generals – to the enigma machine in World War II, and the ability to communicate securely and preserve secrecy have been extremely valuable. Aand a lot of work has sort of been driving most of the work in encryption over the years.
However, I would say that actually this is the secondary benefit that we get from it – the ability to communicate secretly at this stage is less important than some of the other features that we get from cryptography.
And that the most important one is the trust – being able to establish trusted relationships and have trusted and authentic communications with people out in the world and out on the Internet is actually more valuable to society, more valuable to the Internet than just being able to do things secretly.
Most of the quantum cryptography and classical-cryptography models low are sort of stuck in the old way of thinking about things that are very secrecy-centric instead of trust-centric. And so, they always start out with this idea of Alice and Bob where you have two parties who are trying to communicate with each other secretly and then there’s a third eavesdropper named Eve who is trying to listen in.
And my caution is to be wary when this model comes up because it is sort of overly simplistic and doesn’t capture all of the nuance and value of the relationships and transactions and communications that we really want to have.
So, if we expend our resources just trying to provide or rebuild the existing Alice and Bob model then we will come up with a technology platform that is insufficient for our needs – that doesn’t actually give us all of the things that we expect from the cryptography systems that we have now.
And that it’s just too limiting – there’s too many assumptions like okay I can have a classical and a quantum communication channel between these – between Alice and Bob but they are already authenticated. And so, the trust relationship here is implicit. I don’t actually have to solve for that using my quantum systems – and so that’s something that we’re going to need to address as we develop these architectures in the future.
Digital signatures are the basis of that trust. They’re the tool that we get from public-key cryptography that allows us to have software updates that come onto our phones and make sure that we don’t have malware, where the Apple Store is signing each of the apps before they get pushed into your phone and so they can be authenticated, and we know that the software that we’re running is authentic – it is what they say it is.
If you think about the mode of distribution, there is a broadcast mode. It’s not a one-to-one – Alice and Bob – kind of thing; it’s one to many. It’s the Apple Store to the world. We don’t care about preserving secrecy in that relationship because it’s being broadcast to everyone. It’s publicly distributed. But what we do care about is that it’s authentic. That if something – if someone tries to intervene then there’s not an opportunity for them to inject something corrupt.
So, all of that infrastructure – all of that artifice of cryptography and the public-key infrastructure ends up in this green lock icon. Which seems like a very – it only takes a handful of pixels on our screen but actually an enormous amount of infrastructure goes into making that little lock. But what I want to remind everyone is that this lock is not technology, it is actually magic.
It is based on that artifice – the fact that we allow ourselves to send money to people, to transact with our banks, to transact with our loved ones and that we put trust in and we invest resources into it is all based on this: our belief that large numbers are hard to factor into their primes.
And so, if we stop believing that or if something challenges that then this green lock no longer works. It doesn’t allow us to keep investing those resources into it anymore, and so we have to protect that.
And so, as Dr. Miller pointed out, Richard Feynman, one of the inventors and a forefather of quantum computing, came up with his idea and noticed that we were getting a lot of benefit by using computers to model the physical universe which worked really great for classical physics for doing Monte Carlo simulations and for solving systems and equations but fundamentally if you want to model the quantum mechanical universe you’re going to need a quantum mechanical computer -- that a regular computer just doesn’t have the complexity to model the quantum mechanical universe.
And so, if you could build a quantum mechanical system that you could control with the same degree of flexibility that you could control a regular computer you could use that to model other quantum systems and learn things about the quantum mechanical universe.
So, there have been a lot of debates recently about whether or not the universe that we are living in is a simulation or not. And people say things with very high-sounding conviction, but I don’t think there’s any way to really know whether we’re living in a base universe or a simulation.
But I will say that if we are living in a simulation the computer that it’s running on is definitely a quantum computer; right? Which might tell us that the universe – that the actual base universe has quantum physics that is very similar to our own and that it can pass through onto the quantum simulation that are running on.
Be that as it may, the quantum simulation or the quantum universe that we are in lets us do some pretty amazing things. So, Peter Shore developed this algorithm in 1994 and it allows a quantum computer as sort of described by Feynman to be able to factor large numbers into their primes and so it sort of challenges that believe that our cryptography systems are based on.
And it does this by transforming a factoring problem into a periodicity problem -- by looking for if you have a wavey or you have a signal how often does it repeat? And that sort of wave kind of question is something that quantum computers are very good at answering. And so, I came up with this algorithm that can exponentially faster answer those kinds of questions than a classical computer can.
And so, although this was the first quantum algorithm to really be proposed or be written it will probably be one of the last ones to be run. In that as we are developing quantum computers and now they will have a handful of bits and we expect that to grow as we develop the technology and scale it more, the size of quantum computer that you need to solve the factoring problem is still quite large even by quantum computer standards – even though it’s exponentially faster than a classical computer.
So, the expectation is that we will run sort of quantum simulations, quantum chemistry and some of the other algorithms first on smaller quantum computers as they build up, but eventually we will get to that place where an RSA-sized key is able to be factored by a quantum computer and so that’s where we are heading.
So that’s sort of tells us that quantum mechanics is a little bit like alcohol in a sense in that it is both the cause of and solution to all of life’s problems. It creates a lot of difficulty for us in that we’ve built this public-key infrastructure – on the Internet quantum mechanics comes along and smashes that.
But it also gives us a lot of really great tools for building new systems that allow us to have secret and authentic communications with each other and with people in the public and on the Internet. But unfortunately, or fortunately they look very different and have very different properties. And so, as we make that transition we have to keep some of those things in mind.
So, one of the first technologies that we were able to develop that use the quantum properties to give us some of the benefits of public-key cryptography although in a very different mode is quantum-key distribution as developed by folks like Charles Bennett, Giles Brassaurd, Artur Ekert; some other folks. It’s very great for secrecy in that the guarantees that it makes about having a communication between two folks as long as you sort of follow the rules of the protocol are absolute.
There are no unproven mathematical conjectures at the heart of quantum-key distribution the way that there are at the heart of RSA. That it only relies on derivable math and experimentally-verified physics and there’s nothing else in there – which we feel very secure about. So, we would classify quantum-key distribution as not magic – that it is definitely in the technology category.
So, it’s really great for secrecy. The problem is that kind of difficult for trust. So, quantum mechanics fundamentally has some very unique features that make it great for secrecy including the Heisenberg Uncertainty Principle which says that you can’t measure both the position and the momentum of a particle at the same time.
And so, it sort of tells us that the universe is very good at keeping secrets – that quantum mechanics put fundamental limits on what is knowable in the universe. And so those limits are usable, are leverageable by us in designing protocols to keep secrets from other folks.
And so that gives us a very, very, strong kind of guarantee when we are exchanging secrets with each other because we have the universe at our back. We’re using the universal mechanisms – the quantum mechanical mechanisms for secret-keeping in our favor.
On the other hand, though quantum mechanics also has a principal called the no-cloning theorem. The no-cloning theorem states that quantum states can’t be copied. So, unlike say if I write a number down on a piece of paper and I hand it to you it’s very easy for you to copy that number onto another piece of paper and go and distribute it; but in quantum mechanics that’s not possible. If I hand you a quantum state – a fully-coherent quantum state – it is not possible to make an exact copy of that without destroying the first one.
And so that prevents the lot of the normal modalities of communication that we are used to – the sort of one-to-many kinds of modalities where being able to copy and distribute information is so core to how we do things like digital signature distribution and public-key infrastructures. And so those kinds of architectures can’t be applied to quantum protocols because the no-cloning theorem prevents those quantum states from being copied.
In fact, just this week there was a flaw found in the WPA2 protocol which is the sort of normal authentication enterprise-level authentication that all of our Wi-Fi devices use. And the way the attack works is a key-replay attack. So, during the handshake process an attacker can replay the key during the protocol and cause the key to be loaded into a known state.
If we were using quantum Wi-Fi this would not be a problem. The key-replay attacks would be ruled out because of the no-cloning theorem. So, it’s great for that kind of secrecy but it causes problems some of the trust.
When we were trying to build this, the public-key infrastructure that we have where we have registrars, signing signatures, and you know that I go to a website and I create a relationship with a new person that I’ve never transacted with before. This is a very difficult thing to do because of the – with the no-cloning theorem and that prevents the kind of distributing of the quantum states.
If I try and engineer my way around that by just creating many copies of the quantum state and distributing those myself then an attacker can go and collect all those up and use algorithms like quantum-state estimation and quantum tomography and sort of negate a lot of the benefits that I had from making this be a quantum protocol to begin with. So, those things are sort of at odds with each other and so we have to be extra clever about how we design our trust infrastructure.
Another interesting feature that quantum computing has – that quantum mechanics has is that we have to keep in mind as we are developing our new secrecy on and trust infrastructures is this idea that it is reversible. That unlike in say a normal computer if I have some input and I have some output and I know what the steps were that with a quantum algorithm – if I know the steps and I know the output I can always run the steps back in time to get the input. That there has this sort of time reversal symmetry sort of property which we don’t see in classical computing.
In fact, you can kind of think of it like a Rubik’s cube where all of my quantum computations are simple rotations – I can represent them as rotations into some very large dimensional space. And so, if I start with a Rubik’s cube that’s jumbled up and I do some rotations to it and I solve it and I give it to someone and I tell them what the rotations were, they can just undo each of them one by one and hand it back to me and I will have the same jumbled state that I started with; which is not possible with just a regular classical computer program.
In fact, the fact that it’s not possible is something we rely on in cryptography where we have one-way functions. We have hash functions that are fully avalanched – all the bits depend on all the other bits but it’s computationally impossible to go backwards, even if I know what all the steps that were taken were and I know what the out-steps were. Because in classical information – in classical computing information gets erased on the way; it gets thrown off as heat and in quantum computation that doesn’t happen.
There’s sort of nothing wasted so it’s very efficient but at the same time if I’m using that heat, that erasure as part of the benefit of my algorithm then it’s not going to show up. So, I have to be aware that when I’m designing my system I can’t just simply upgrade the algorithms I already have into the quantum world because doing so would make them reversible and therefore not useful for the same kinds of quantum primitives that we are accustomed to.
So, one of the ways that this really shows up is with the Bitcoin network. We are already deriving a huge amount of tangible benefits from being able to transact and have exchanges of value with people on the Internet with no trusted third-parties, but the protocol was designed on classical computation – on public-key infrastructure as we understand it today and has some features that we need to be aware of. So, the mining of new coins of Bitcoin is based on the SHA-256 hash algorithm.
This turns out actually to be vulnerable by a quantum algorithm called Grover’s Algorithm. However, it doesn’t give us an exponential speed up, it’s only a quadratic speed up so, it’s probably not the fundamental vulnerability for the Bitcoin network from quantum computing.
However, the Bitcoin transactions – if I move something from one account to another account – from one address to another address – those are signed, those are authenticated with RSA public-key keys. And so, once I move money from one account to another then someone – an attacker could see that transaction, get my private key and then all of the remaining money in that account would then be vulnerable – they could come and make a new transaction and steal it.
So, I could imagine perhaps sort of engineering myself around this where I – although Bitcoin itself as we understand it now is definitely magic we sort of have a reduced-magic version of it where maybe I only use each one of my private keys once and then move everything to a new address. And so even if someone figures out my private key later because the quantum computers – it just takes a little bit of time – they won’t be able to make use of that.
It would be a very cumbersome system. It would be like every time you go to the ATM and you withdraw $20 you would have to close your account and move all of your money to a new account so – because that account would be vulnerable from then on. So, you could kind of figure out a way to do it.
But a much better approach would be to sort of just table the architecture that we have now for Bitcoin and think about how should we be really moving money around. If instead of trying to fight against the quantum principles and fight against what the quantum computer represents – actually use the quantum principles in our favor,; and so that’s this idea of quantum money.
This was actually – sort of first proposed by Stephen Wisner in the 70s – perhaps maybe the first real quantum algorithm or study in quantum information before anybody took any of this seriously or really had any idea that any of this was really possible as a sort of thought experiment – that what if you could use things like the no-cloning theorem to provide counterfeit protection for your money?
So, then instead of fighting against the quantum properties and fighting against the quantum computer we now have quantum mechanics working for us where we say that if I am printing my money then the no-cloning theorem prevents anyone else from stealing it or prevents anyone else from copying it.
And so now we have to figure out to develop protocols of what’s the best way to validate the money that I have is really authentic but knowing that the safety and security of it is backed by quantum physics.
And so, this is something exciting that we have to look forward to in that we can have a money exchanging system on the Internet that is extremely secure – and maybe more importantly that is not magic. That is just based on real technology on physics and derived math.
So, in the post-quantum world it is still going to be useful for a while for us to develop algorithms and systems that have some of the features and benefits of things like RSA that give us secrecy and trust but are maybe not as vulnerable to quantum attacks to quantum computers.
Lots of proposals for these things out there – lattice codes, air-correcting codes, multi-variated codes. I would like to point out however that even though there are no known quantum algorithms that can solve these things – although Peter Shore and others are working very hard to try and change that, that all of these things are still magic – that they are still based on unproven conjectures that certain problems are very difficult to go one way more than they are the other. And so, there’s still that risk.
While we are in this transition zone it’s still to keep cognizant in mind that new algorithms can come along, new algorithms will be developed. That quantum computers will get much bigger, much faster. And so, as we are looking to build the trust and communication in security networks of the future – we should be trying to at least go to stronger versions of magic but ideally move off of magic and start using real technology.
So, this is a sketch from Isaac Newton’s notebooks about the Philosophers Stone which was sort of the core piece of magic behind alchemy. He gave it a shot, played around with it – maybe learned some things about chemistry in the process but eventually had to give it up.
And it sort of points to that perhaps that a lot of these things that we’re basing our cryptography systems on that are magic live in the kind of Gödel’s Incompleteness Theorem which says that there must be things in math that are true but not provable; unfortunately, you never really know what those things are so it’s hard to kind of count on them.
But the idea is that Newton went through this transition period of looking at magic and exploring it and learned a lot of things from there but eventually moved off of that and got into real science. And so, I hope that we can make a similar transition. We’ve rubbed the lamp, we’ve made some wishes, we’ve got some really great benefit out of public-key cryptography but now that quantum computers are starting to become a real possibility that we need to be cognizant of how we build our systems.
I’m going to end back where I started with Arthur C. Clarke. So, we started with his third law – this one is his second which I think is probably a little bit more true. So, the only way of discovering the limits of the possible is to venture a little way past them into the impossible; Arthur C. Clarke’s second law.
And so that’s what I’d like us to do here today and looking for that as we look a little bit past what we think the impossible is with developing quantum computers and figure out where that boundary is.
Thank you very much.