The quantum revolution: Q-Day

This is an audio transcript of the Tech Tonic podcast: ‘The quantum revolution — Q-Day’

John Thornhill
Imagine a machine that can do the seemingly impossible.

[MUSIC PLAYING] 

A computer that can perform calculations that no other computer can perform. A computer that can solve problems we used to think we’re just unsolvable. A computer that seems to operate outside the normal bounds of time and space. They’re building computers like that right now in tech companies and research labs around the world. They’re called quantum computers. And the people building them say they’re going to change the world. I’m John Thornhill.

Madhumita Murgia
And I’m Madhumita Murgia. We’re both journalists at the Financial Times, and for years, through our reporting, we’ve been hearing that quantum computers — computers that operate in the realm of quantum physics — are coming. And when they finally arrive, they’re going to be revolutionary. They’re going to redefine what’s possible with a computer, and they’re going to upend whole industries, everything from finance to pharmaceuticals, with their awesome power.

John Thornhill
We want to find out if that’s true. If quantum computers really do represent a computing revolution, and what that might mean for the world?

Madhumita Murgia
So that’s what we’re going to try and do over the next six episodes of this series. But quantum computing is complicated. So we want to start with a simple example of a quantum computer’s potential power, an example where a quantum computer could do things that other computers can’t do. And the best example is all to do with cracking passwords.

(keyboard punching sounds)

Mark Carney
There’s almost always someone who’s got a password of password somewhere. Or really common is what I call swipe to unlock, which is one, two, three, four, five, six, seven, eight. There’s lots of passwords that are usually like that.

Madhumita Murgia
This is Mark Carney. He’s a cybersecurity researcher at a major bank. But before that, he worked as a professional hacker, testing the security of IT systems by trying to break into them. And for him, cracking a password is usually pretty straightforward.

Mark Carney
The phrase password is deeply unhelpful because it means that you use a word — first names, for example, towns and cities in the UK, the four or 5,000 most common English words.

John Thornhill
The fact that people tend to use words means Mark can use lists of common words to guess your password. To do that, he uses a password cracking program on his laptop.

Mark Carney
So what it’s doing is you can see it’s trying different things. It’s just going to take every word in that list and then just keep chewing through passwords until it finds a break.

John Thornhill
So the way that program works is to try one password (keyboard punching and then error prompt) and then another (keyboard punching and then error prompt) and another (keyboard punching and then error prompt) until it stumbles on the one that works (password accepted chime).

Madhumita Murgia
And if you’ve tried to be clever and added an exclamation mark to your password or maybe change some of the letters into numbers. Mark and his laptop have that covered, too.

Mark Carney
I know that it’s a common substitution to replace the letter O with a zero, a letter A with a number four, for example. You can also add special characters anywhere. You can add capital letters.

John Thornhill
So the laptop crunches through all these possibilities one by one. It’s what hackers call a brute force attack. Mark’s laptop is making a million guesses a second. To get the right answer, all he needs is time.

Mark Carney
This going to the whole thing will probably take a few hours. It’ll probably work, but it’ll take a few hours. I guess we’ll just see.

[MUSIC PLAYING] 

Madhumita Murgia
But there are passwords that Mark and his laptop will find almost impossible to crack. Instead of a word, you could use a string of random characters. It means that instead of trying every word in the dictionary, the computer program has to go through every possible combination of characters. And if your random password is, say, 12 digits long, the number of possible combinations is in the billions upon billions upon billions.

Mark Carney
There’s no shortcuts. Using words gives you a shortcut because words are predictable. Whereas random passwords, there’s no help. You just have to go through everything for one character, then through all that again with another character, and then keep going. And keep going and keep going.

John Thornhill
Even at a million guesses a second, Mark’s laptop would take a really, really long time to find the right answer.

Mark Carney
That comes out as 8bn Gregorian years. I think the sun might be dying a bit by then.

John Thornhill
This is what makes random passwords so strong. It just takes too long to guess the right answer.

Madhumita Murgia
But what if Mark didn’t have a laptop? What if instead he had a quantum computer?

Mark Carney
Haha! That’s where things get really interesting.

John Thornhill
A quantum computer would be really, really good at guessing passwords. That’s because it doesn’t work like a regular computer. It doesn’t have to go through every possible combination one by one. Instead, it does something amazing. It takes all the billions of possible combinations of that random password and considers them all at the same time. And then it just zeroes in on the correct one. And suddenly, guessing a password doesn’t take 8bn years.

Mark Carney
I think speaking optimistically about how a quantum computer could handle it would be order of minutes. I think a quantum computer could do it potentially, if it’s a good one, within just a few minutes.

Madhumita Murgia
This is what is so incredible about quantum computers, their ability to consider all this information at the same time and find shortcuts to problems that should take billions of years to solve. It’s why quantum computers are predicted to be so revolutionary. You could apply that power to all kinds of problems, making better trades on the stock markets, developing new drugs, even finding solutions to climate change. But it’s also what makes them so potentially dangerous. Because when it comes to encryption, it turns out quantum computers wouldn’t just crack the 12-digit password you might use to log in to your computer system. They would crack all kinds of codes. They could even crack the codes that underpin the security of the entire internet.

[MUSIC PLAYING] 

John Thornhill
This is Tech Tonic from the Financial Times, a podcast about how technology is changing our world.

Madhumita Murgia
This season is about quantum computers. And this is episode one, How quantum computers might break the internet.

John Thornhill
OK. Right at the beginning, we should say that quantum computers don’t really exist yet. Or rather, they do exist, but the ones being built right now are essentially prototypes. They aren’t powerful enough yet to do anything really groundbreaking, but we’re told it’s only a matter of time until the day when a really powerful quantum computer emerges.

Madhumita Murgia
In the cybersecurity world, they call that day Q-Day. The day when someone builds a quantum computer with the capacity to break the encryption that underpins the internet.

[MUSIC PLAYING] 

John Thornhill
The reason quantum computers should be so good at breaking encryption is because they work in a completely different way to the classical computers we have today.

Madhumita Murgia
Classical computers encode information in bits. Each bit is either a one or a zero. Quantum computers also have bits called qubits, and they exist in a weird quantum state where they are both zero and one at the same time. And that means a quantum computer can represent all the different combinations of ones and zeros simultaneously.

John Thornhill
That’s why a quantum computer can consider all the possible combinations of a random password at the same time, rather than going through every combination one at a time like a classical computer has to do. Another analogy that’s used a lot is trying to find your way out of a maze. A classical computer has to methodically walk down every dead end until it finds its way out. A quantum computer head straight for the exit.

Madhumita Murgia
But when it comes to the encryption on the internet, a quantum computer’s ability to break a 12-digit password isn’t really what’s at stake here. Much of the encryption on the internet today is based on a problem that’s even more difficult to crack.

John Thornhill
Right, it’s an algorithm called RSA.

[MUSIC PLAYING] 

RSA dates from the 1970s. It presents would-be hackers with the challenge. Here is a really long number. Hundreds of digits long. There are only two prime numbers that, when multiplied together, give you this long number. And to break the encryption, you need to find those prime numbers. Working out what those numbers are is called factoring. And it turns out it’s just extraordinarily difficult to do. There are just too many possibilities to consider. Mark Carney, who we heard from earlier, says this problem is so hard that even all the classical computing power in the world wouldn’t be able to solve it.

Mark Carney
The number of possibilities is enough that I couldn’t describe it in billions, billions, billions. And so, again, a classical computer has just churn through everything over and over and over and over again. And even with all the GPU power and CPU power of, you know, Amazon Web Services, it would not be a particularly tractable problem. It’s hard enough that it would take, in a very naive sense, to the end of, yeah, pretty much end of the universe stuff.

John Thornhill
And so for years, RSA was assumed to be practically unbreakable until this guy came along.

Peter Shor
Hello, I’m Peter Shor. I’m a professor in applied math at MIT.

John Thornhill
Peter Shor is a legend in the world of encryption and quantum computers. He’s also a published poet. So I had to ask him to read a poem.

Peter Shor
So I guess the most famous one is probably my limerick about quantum computers. So that goes, If the computers that you build are quantum, spies of all factions will want them. Our codes will all fail. They’ll read our email. Till we’ve crypto that’s quantum and daunt ‘em (chuckles).

Madhumita Murgia
There you go. Quantum computing as literary inspiration.

John Thornhill
I like his poems, but the contribution Peter Shor is really famous for came in the early nineties. At the time, no one had built even a prototype quantum computer, but people could still do the math to understand how they would work in theory.

Peter Shor
In 1992, 1993, people were looking at these hypothetical machines based on the principles of quantum mechanics called quantum computers. And so I started thinking about whether there was any way to use these machines to solve a problem that people actually cared about.

John Thornhill
Shor started looking at the factoring problem.

Peter Shor
The RSA algorithm uses factoring, and if you could factor large numbers into primes, you could break this crypto system. And nobody knows a really good way of factoring large numbers in primes on a digital computer.

John Thornhill
So Shor worked out an algorithm that showed that if you had a quantum computer, you could use it to factor these large numbers and break RSA.

Peter Shor
So I came up with the algorithm, I guess, some week in April of 1994. And then he gave a talk about it. And news of this spread so fast that within a few weeks I was getting deluged by emails from people asking for the paper, which I hadn’t actually written yet. Everybody was very interested. There was someone at the NSA came up after my talk and asked me questions about it.

[MUSIC PLAYING] 

John Thornhill
This was a massive moment. No wonder the NSA, the National Security Agency, had questions, even though quantum computers didn’t exist yet, the mere idea that one would be able to break RSA was deeply worrying. Suddenly, the security of the whole internet is at risk.

[MUSIC PLAYING] 

RSA is used all over the internet. In web browsers, it’s used to keep emails secure. It’s used in banking transactions, in computer systems that control power grids and water supplies, even in government communications. The fear is that if some bad actor, a hacker or a hostile state, got hold of a quantum computer, they could cause havoc with the political and economic system. So if you were the American government, you might be wondering what would the Chinese do with a quantum computer that could hack into everything? And if you were the Chinese, you might be wondering the same thing about the Americans.

Madhumita Murgia
Of course, no one has actually built a quantum computer that could run Shor’s algorithm and break RSA. Most estimates say that day, Q-Day, is probably years, if not decades away. But that doesn’t mean we can just put off worrying about the quantum threat. Governments and hackers could already be getting a head start. They could be harvesting large amounts of encrypted information today for a quantum computer to decrypt later.

Jack Hidary
If I am a state sponsored actor or an independent actor and I want to find information that I could store now to decrypt in the future, I don’t even have to break into their computers.

Madhumita Murgia
Jack Hidary used to work for Google. These days, he’s the boss of a quantum technology company, SandboxAQ. And he says that governments and private companies alike are already vulnerable to quantum attacks. Imagine you’re a big pharmaceutical company, say, and you’re transferring information about your blockbuster drugs between your offices. A hacker could simply tap into that stream of information and siphon it off.

Jack Hidary
I can’t read it today because indeed it is encrypted, say with RSA, but I can store it and then retrospectively decrypt it in a number of years when I have advanced computing power. And so this means that if it is IP, intellectual property, if it is in fact confidential government information, if it is in fact the architecture of the energy grid that you are transmitting and and going back and forth, then indeed, this is information that’s still valuable years from now.

Madhumita Murgia
Jack says that this all means we need to start working out how to protect ourselves from quantum attacks today.

Jack Hidary
We know that it takes about 10 to 15 years for governments and banks to change over to new standards. And so when we think about the fact that quantum will break the RSA protocol and people say, well, Jack, you know, we don’t have the computers of today to do that, but we know that it takes 10 to 15 years to change over in the largest of enterprises. And this is the critical infrastructure of our society — the telcos, the banks, the hospitals, the governments, the energy grid. So the time to start is now because it takes years for this to happen.

John Thornhill
So how do we protect ourselves against the threat of a quantum computer that might be built at some point in the future that might one day be used by some hostile agent to break all our encryption?

Madhumita Murgia
Well, the solution might actually be really simple, better mathematics.

Dan Bernstein
Shor’s algorithm suddenly saying, if somebody builds a big quantum computer, then, yikes, you can factor really big numbers really quickly. And it’s not that we have a big quantum computer yet, at least not publicly, but as soon as one comes, this is a gigantic threat that can destroy the security of all sorts of internet communication.

Madhumita Murgia
This is Dan Bernstein, also known as DJB. He’s a research professor at the University of Illinois, and he’s one of the most eminent cryptographers in the world. And today he’s among the group of cryptographers working on what’s called post quantum cryptography. The idea is to replace RSA and all the encryption systems vulnerable to quantum computers with new forms of encryption that aren’t. That means creating mathematical problems so difficult that even a quantum computer can’t solve them. In 2016, a US government agency called the National Institute of Standards and Technology, or NIST, decided it needed cryptographers like Bernstein to help come up with these new quantum safe forms of encryption. So it ran a competition.

Dan Bernstein
They said, alright, everybody’s free to submit something to this competition, and we’re going to have an open process and evaluate all these submissions. And 200 cryptographers submitted all sorts of proposals.

Madhumita Murgia
This public competition was a big deal in the cryptography community. NIST eventually got about 70 proposals from cryptographers around the world for crypto systems that might stock quantum computers. So it released details of them and then the community went about testing them to see if they really were as unbreakable as they were supposed to be.

Dan Bernstein
And then it’s been demolition derby since then.

Madhumita Murgia
It sounds mean, but this is how cryptography works. You come up with a code, say it’s unbreakable, so someone else tries to break it.

Dan Bernstein
People say, here is a crypto system that I think has the following security properties. Like, I think this crypto system protects against quantum computers. And then somebody else comes along and says, well, actually here’s an attack which shows that we can break your crypto system in a weekend on a laptop.

Madhumita Murgia
Initially, it didn’t look like the competition was going too well. Supposedly, quantum-safe encryption systems were being cracked all over the place. Take the example of one encryption system called Sike, which NIST seemed to think had potential.

Dan Bernstein
Now, CYC is a crypto system that NIST had said, Oh yeah, we’re continuing to consider that one. It looks good. It’s got some attractive features. And then suddenly, July 2022, the system was totally broken.

Madhumita Murgia
About half of the new encryption systems turned out to be breakable. But eventually, after all the carnage, last year NIST came up with four encryption systems that they recommended people use to protect themselves from quantum computer attacks.

John Thornhill
If they work, it’s problem solved. Our encryption is quantum safe. But even Dan Bernstein, who spent his entire career building encryption systems, is far from sure that post-quantum cryptography will work.

Dan Bernstein
For protecting against quantum computers, I think that this is the best hope that we have. I mean, it’s the best approach that I see in terms of managing the risks of quantum computers. It’s not like we have an alternative, but the reality is we have made so many mistakes for so many years that we’re just, in general, cryptography is not doing a good job.

John Thornhill
The worry for Dan is that encryption is never completely safe. And with quantum computers, we just don’t know what they will really be capable of in the future. It’s possible that encryption that looks quantum safe today won’t be quantum safe forever.

Dan Bernstein
We can never be 100 per cent sure. And we have to worry that somebody is going to come up with a way to use quantum computers that’s better than what we thought of. And that breaks the things that we’re thinking today are secure against quantum computers.

Madhumita Murgia
But even if post quantum cryptography doesn’t work, there is always the possibility that no one actually builds an encryption-cracking quantum computer, and Q-Day never comes to pass. The primitive quantum computers around today are no good at breaking RSA. Some of them have been able to do the factoring problem, but the biggest number they’ve been able to factor so far is 21. That’s a long way off the 600-digit numbers that RSA uses.

John Thornhill
Peter Shor, the man who started all this by showing that hypothetical quantum computers could break RSA, isn’t himself certain that real quantum computers will definitely be able to do it.

Peter Shor
You know, early on, it looked like quantum computers would basically be impossible to build. I mean, it’s taken, what is it, 30 years? But now people are building, you know, toy quantum computers that really seem to work. I mean, they only have a few hundred qubits so far. To factor, you need probably at least 100,000 and probably more like a million or several million qubits to crack RSA. And there’s a huge amount of engineering and probably breakthroughs in physics and breakthroughs in mathematics and computer science before this actually becomes a reality.

John Thornhill
What’s your best guess as when we might have a quantum computer that could run your algorithm?

Peter Shor
I would predict between 20 and 40 years. I mean, it really depends on how many breakthroughs people make. If you could reduce the number of physical qubits required from a few million to a few hundred thousand, that brings it a lot closer. If this continues, which is going to require some engineering breakthroughs to make it continue, then we should definitely have quantum computers in a few decades. If it doesn’t continue, then we’re in trouble. We may never build quantum computers because, you know, it’s a really tough engineering problem.

John Thornhill
And you think that’s a real possibility that just the physics will be too hard?

Peter Shor
I think that’s a real possibility, although I’m fairly optimistic right now that the improvement and the precision is going to keep on improving. And if that happens, I’m sure we will actually get quantum computers at some point.

John Thornhill
Are you incredibly impatient for this computer to turn up so that it can actually run your algorithm?

Peter Shor
I would really like it to turn up sometime in the next decade or two, but I’m not at all sure that it will.

Madhumita Murgia
So Peter Shor is hopeful of seeing a quantum computer that can do what he predicted it could do, run his algorithm. But the cryptographer, Dan Bernstein, is less keen.

Dan Bernstein
I mean, honestly, as a cryptographer, I would love for quantum computing to just fail horribly because all the benefits that I’ve heard about from it compared to the damage that quantum computers are going to do . . . Well, if quantum computers can’t be built, then we’ve really dodged a bullet there.

John Thornhill
There may not be a fully functioning quantum computer that can threaten encryption out there yet. But unfortunately for Dan Bernstein, there are a lot of people out there working on it, and they say it’s just a matter of time.

Madhumita Murgia
Next week on Tech Tonic, the race to build a quantum computer.

Erik Lucero
And you’re looking at a prototype of that system. And how is this going to grow when we go from, say. 100 qubits that we have today to a million physical qubits in the future?

Madhumita Murgia
 . . . and the tech companies that believe quantum computing will change the world.

Krysta Svore
When we think about the challenges facing humanity, these types of problems require an advanced technology that we don’t have today. And quantum computing will enable us to solve these types of problems that impact all of us.

John Thornhill
You’ve been listening to Tech Tonic from the Financial Times. This series was presented by me, John Thornhill . . . 

Madhumita Murgia
 . . . and me, Madhumita Murgia.

John Thornhill
Our senior producer is Edwin Lane, and our producer is Josh Gabert-Doyon. Manuela Saragosa is executive producer, sound design and engineering by Samantha Giovinco and Breen Turner. Original music by Metaphor Music. The FT’s global head of audio is Cheryl Brumley.

Madhumita Murgia
This is the first episode in this season of Tech Tonic on quantum computing. We’ll be back over the next five weeks with more. Get every episode as it lands by subscribing to Tech Tonic on your usual podcast platform. And one last thing before you go, we want to hear from you. We’re keen to hear more from our listeners about the show and want to know what you’d like to hear more of. So we’re running a survey which you can find at ft.com/techtonicsurvey. It takes around 10 minutes to complete, and you will be in with a chance to win a pair of Bose QuietComfort earbuds. We appreciate your feedback.