Can we build quantum-resistant encryption?
Connecting state and local government leaders
New research demonstrating that quantum computing is now just an engineering challenge moves the possibility of encryption-cracking machines to the front burner.
The possibilities and problems of quantum computing have figured more in science fiction than they have in government security, but that is gradually starting to change. The impact of quantum computing on cracking encryption schemes has long been debated, at least in concept, but now some are calling for government to take a more active role in mitigating that possibility.
The push for some action may get stronger after a recent announcement that computer scientists at the Massachusetts Institute of Technology and the University of Innsbruck had assembled a quantum computer that could eventually break RSA (Rivest-Shamir-Adleman) public key encryption, the most popular form of encryption in the world. What’s more, they did it with a calculation that used just five quantum bits (qubits), far fewer than had been thought necessary.
A qubit is a unit of quantum information, analogous to the on/off bit used in classical computing, although in the “spooky” universe of quantum mechanics (as Einstein put it) a qubit can be in both states at the same time. It’s by manipulating that property that quantum computers can do some kinds of computation very efficiently, such as factoring very large numbers.
Current encryption methods, such as RSA, depend on the difficulty of doing all that number crunching. A public key is the product of two very large prime numbers, known only to the key provider, and cracking the encryption requires factoring, or breaking down, the key to reveal those two numbers. That’s very hard and would require years’ worth of computations with classical computing, even with the help of a large parallel computer.
It’s not as if quantum computers that can break public key encryption will here tomorrow. The MIT/Innsbruck effort was aimed at developing a method to factor the number 15, which was thought to require 12 qubits. That was considered the smallest number needed to meaningfully demonstrate Peter Shor’s quantum factoring algorithm, which was developed several decades ago.
And building the quantum computer, which requires a complicated setup of lasers, gases and such things as ion traps, was not simple. However, the MIT/Innsbruck team built their system to scale so that it can eventually handle much larger prime numbers. The fact that they reduced the resources required for that work by a factor of three should make that easier.
A quantum computer capable of factoring the numbers behind RSA and other encryption methods may still be another decade away, but that’s substantially less than the 20 to 30 years many had figured it would take. Some experts are already concerned that there may not be enough time to prepare adequately for the arrival of those large-enough quantum computers.
At a meeting last year, for example, computer security specialists discussed what cryptographic schemes would be required to resist quantum computers. Some openly worried that there wasn’t enough time -- given all the detailed discussion between governments and industry that will be needed -- to develop the proper protections.
At the meeting, Stephen Jordan, a physicist at the National Institute of Standards and Technology, stressed that you need a lot of people to scrutinize and test any cryptosystem for flaws if it is to be trusted, which “takes a long time.”
Some parts of government are not waiting, at least to set things in motion. At the beginning of this year, the National Security Agency’s Information Assurance Directorate published a FAQ aimed at giving national security system (NSS) developers the information they’ll need to begin planning and budgeting for new cryptography that is quantum resistant.
The IAD warned that, especially in cases where government information needs to be protected for many decades, “the potential impact of adversarial use of a quantum computer is known and without effective mitigation is devastating to NSS.”
One thing the MIT/Innsbruck team proved is that the development of quantum computers that can break very complex encryption is no longer theoretical.
“It might still cost an enormous amount of money to build, [and] you won’t be building a quantum computer and putting it on your desktop anytime soon,” Isaac Chuang, professor of physics and professor of electrical engineering and computer science at MIT, said in announcing the team’s accomplishment. “But now it’s much more an engineering effort and not a basic physics question.”