Quantum Computers Are a Bank Robber’s Best Friend
The quantum apocalypse is not imminent. You can bank on it!
The thief emerges from the dark stone passageway and finally beholds the mighty sphinx guarding the way. Behind it lies unspeakable wealth, but the thief knows the stories. The sphinx will pose a riddle, and only if he can answer it correctly will he be allowed to pass. None have ever solved this riddle. It is said to be so hard that a man could spend a million lifetimes pondering it and still not come close to the truth. As the thief approaches, the sphinx looks up and utters its question: “Apart from one and itself, what two numbers can be multiplied together to give the number: 24173714133020249347155858743127780309174339406635435964399085347656982387720954688039452436493114578916020871870165351007011870999178785887526253389052486220723581359659032380423037556354151437036605740095801765443143301937101209454368287545987373643365686082094060182698050888884868747964149630456114713056032329052280347875981424413023214140696559616756565815168454414522637600183472584158079642337617145105009591477490614132844440590363168345097611163565817773710708326926604916214306434900543563743653414367155768580711992894418225727834712262716423863154780980335325178621353574178445755044479153560747446027023?”
Could you answer this question? If so, then you too could claim riches beyond imagining. In fact, you could do it from the comfort of your own home. By entering the answer into the right software, you could gain access to any Commonwealth Bank of Australia account, and empty the contents into your own. Fortunately, it remains true that no one has ever solved the puzzle, and that with present technology it would take trillions of years to do so. However, the thief who could do so may only be a matter of years away. All they would need is a quantum computer.
The Key to Secure Banking
Whenever you access your bank account online, you are asked to enter a password (or PIN). Since you are the only person who knows this password, entering it serves as proof of your identity. The password you enter is sent to the bank’s computer which checks that it is correct and, only if it is, gives your computer access to your account. This is an effective system, but it has an important security risk; your password could be intercepted as it is transmitted across the internet to the bank. Anyone who successfully intercepted the password in this way could easily log in to your account themselves and steal all your money.
To avoid this, the password must be encrypted before it is sent. This is done using a protocol called RSA. Each organisation for which security is paramount – such as banks or government services – have their own unique 617-digit number, called a public key. The number in the sphinx’s riddle is the public key for the Commonwealth Bank of Australia. Every time you type your password into the bank’s website, your computer puts the password, along with the bank’s public key, through RSA encryption software. The software outputs an encrypted version of your password which is then sent over the internet to the bank. The only way to determine your actual password from this encrypted version is to enter another number – called the bank’s private key – into the RSA software. The bank know their own private key, so they are able to verify the password you submitted. But the private key is kept completely secret from absolutely everyone else. This is the crux of the system; as long as no unauthorised actor knows the private key then your account is secure. But if anyone ever finds out the private key, then they could use it to read the passwords needed to access all of the bank’s accounts. So, the safety of your money depends on the guarantee that no aspiring bank robber could ever work out your bank’s private key.
.jpg){kind=link}
Unfortunately, this guarantee cannot be given with absolute certainty! Digital encryption systems, like RSA, are analogous to using a lock and key to protect information in a safe. In order to access the safe, you need the key; this key is like the private key of RSA. While the key is kept secure, the lock on a safe can be examined by anyone with access to the outside of the safe; this lock is like the public key of RSA. The security risk is that, because the lock and key must match for them to function, examining the lock could theoretically allow a person to determine the shape of the key. This information could allow anyone to make a copy of the key and open the safe, even without ever having had access to the original key. The same is true of digital encryption. It is theoretically possible to calculate the private key needed to rob the bank by examining only the public key published on their website.
Specifically, the private key is one of the factors of the public key – i.e., a number that can be multiplied by another number to give the public key as the product. This is why answering the sphinx’s riddle would allow you to rob the bank. The sphinx is asking for the bank’s private key! If you enter the answer into RSA decryption software, you could find out the passwords needed to access any of the bank’s accounts. So, should you rush to the bank, withdraw all your money, and stuff it in a mattress? It depends on the answer to the question: how difficult is it to find the factors of a 617-digit number?
Your Money is Safe… For Now
Fortunately, factoring large numbers is incredibly difficult. The factoring methods we learn at school are essentially trial and error; we first test if two is a factor, then test if three is a factor, and so on. The problem is that this takes a long time, especially as the number of factors we have to try grows quickly as the number we are factoring becomes bigger. For example, factoring the 3-digit number 143 only requires testing five numbers, but factoring the 4-digit number 4757 requires testing nineteen numbers, and factoring the 5-digit number 79523 requires testing sixty numbers. How many numbers does factoring a 617-digit number require us to test? Over 10305 (a one followed by 305 zeros)!1 This is why, even with the help of a computer, and the best-known techniques, it is estimated that factoring a 617-digit number would take 300 trillion years. If a would-be bank robber started the process now, they would only be 0.002% complete by the time the Sun consumes the Earth. This is why your money is safe in the bank! At least for now…
Fundamentally, factoring a number is difficult because it cannot be done digit by digit. For example, you cannot determine that three is a factor of 231 by looking at the digits individually: each digit of 231 is contained in either 230 or 131 but three is not a factor of either. Instead, you must use the divisibility rule you may have learnt at school: add up the digits (2+3+1=6) and see that the sum is a multiple of three. This is a general feature of divisibility rules; with a few exceptions, they involve working with all digits of the number. The factors of a number are a holistic property of the whole number that cannot be seen by breaking it down into its constituent digits. Conventional computers and mathematical methods are bad at reading such holistic information, and so are very inefficient at factoring numbers.
However, there is an emerging technology better suited to holistic problems like factoring – quantum computers. Quantum computers exploit the remarkable phenomena of quantum mechanics – which describes the most fundamental particles of nature – to perform operations impossible on conventional computers. In particular, a quantum computer can use quantum entanglement to combine information from across all the separate digits of a number into an extremely complicated state that has no analogue in conventional computing. Because this encapsulates the entire number in a single state, holistic properties of the number like its factors can then be extracted, using another process called quantum interference.
For now, quantum computers remain a technology of the future. However, multiple companies, from ambitious start-ups to established tech giants, have set a goal of building a functioning, first-generation quantum computer this decade. In 2019, it was shown that even such a basic quantum computer could factor a 617-digit number in a single day. So, the first day a quantum computer becomes operational, an unscrupulous operator could use it to calculate the bank’s private key and gain access to everyone’s money! This is why quantum computers are a bank robber’s best friend.
Why Do We Even Want to Build a Quantum Computer?
This naturally prompts a question: why are people trying so hard to build quantum computers? Until 2015, Google’s motto was famously “don’t be evil”. But, on the face of it, spending billions of dollars and recruiting world-leading scientists to try to build “a bank robber’s best friend” sounds like the behaviour of a malevolent supervillain. Why are they doing it? And why are universities, investors and governments around the world all supporting the same goal?
It is because there are also far more noble intentions for quantum computers. These are primarily based on the idea of quantum simulation – reproducing quantum mechanical phenomena to allow for closer study of natural and industrial processes in a way that could advance science and technology. For example, quantum computers could guide the development of more environmentally friendly alternatives to vital but high-emissions processes such as fertiliser production. They could also help advance the development of green technologies such as electric cars and hydrogen fuel production. This has led to a hope that quantum computers could help limit climate change. It has also been proposed that quantum computers could improve our understanding of molecular processes in our body to support the development of new medicines.
Exciting as they are, we may hope that these ideas will prove to be just the beginning. We have seen that quantum computers have potential far beyond their straightforward application to quantum simulation. Their true power is to process data holistically to answer questions that are incredibly inefficient to solve using the more atomistic methods of conventional computers. Factoring numbers is the first application of this. Unfortunately, its implications are destructive; it undermines our online security. However, perhaps this should not be surprising. It is typical that the first applications of revolutionary new ways of thinking are destructive; it is easier to see how to derail the status quo than how to create something new. But given time, new perspectives can empower progress in unforeseen ways. We have reason to be optimistic that the most beneficial applications of quantum computers are yet to be conceived.
In the meantime, we must still reckon with the threat of the bank robber’s best friend. Fortunately, there is no need for panic. New forms of encryption that are resistant to quantum computers have been developed and are already in use for vital applications such as top-secret government data. We can be confident that these will be rolled out as needed by the time quantum computers are operational. While we should not be complacent, contrary to what has been reported in more sensationalist outlets, the quantum apocalypse is not imminent. You can bank on it!
The candidate factors are all prime numbers up to the square root of the 617-digit number. The square root of a 617-digit number is at least 10floor(617/2)=10308. By the prime number theorem, the number of prime numbers less than 10308 is approximately 10308/ln(10308)=1.4x10305.
Really enjoyed this one - thanks Paul