NIST Plans to Fend off Quantum Computers That Will Attack Encryption

We all know about the RSA encryption scheme that uses the product of prime numbers and how it is the backbone of our widespread public/private key cryptography. The reason it works is because classical computers take a very long time to discover which prime numbers were multiplied together to generate the key. And the time needed to programmatically discover the original primes grows exponentially with the number of digits in the key. So while the encryption is theoretically hackable it can be made as difficult as you like by making the key long enough. Now with the prospect of quantum computers on the horizon coupled with several known algorithms to factor these prime products our whole secure encryption scheme falls apart. The main reason it fails is because the quantum algorithms on a quantum computer should require a few seconds to get the prime factors of today's keys. But worse, is that the time it takes to complete the process scales between N and N(logN). So, even with unrealistically long

The cryptography specialists at the National Institute of Standards and Technology (NIST) are already working on that. NIST Internal Report (NISTIR) 8105: Report on Post-Quantum Cryptography describes the current work being done on quantum computers. And they hope to describe a plan to eliminate this security weakness.

NIST mathematician Dustin Moody said "There has been a lot of research into quantum computers in recent years, and everyone from major computer companies to the government want their cryptographic algorithms to be what we call 'quantum resistant." The NIST plan is to proactively prepare some new methods. Moody continued, "So if and when someone does build a large-scale quantum computer, we want to have algorithms in place that it can't crack."

One part of the plan they are proposing is that we make our cryptography more modular. The encryption code that we put in our systems should have a standard plug-and-play architecture so that we can quickly swap them out if we need to. They're referring to this as "crypto agility".

Of course the idea of coming up with newer more secure algorithms is easy to say, but will certainly be difficult to do. How long did it take for the RSA scheme to be developed and eventually embraced? Another big part of the plan is to have an open collaboration with the industry where algorithms can be submitted and the "white hats" can try to break them. As a start they will model their competitions after what was done with the  SHA-3 hash algorithm. 

Moody also pointed out that we would need multiple approaches, there is no silver bullet, "We're not expecting to have just one winner. There are several systems in use that could be broken by a quantum computer—public-key encryption and digital signatures, to take two examples—and we will need different solutions for each of those systems."

Of course, all this relies on the premise that there are other mathematical techniques that are not inherently crackable by quantum computers. We have no proof that these techniques exist, but there is much worldwide research being done on the problem.

It's important to note, that there are no quantum computers that could do this kind of decryption today. But progress is happening quickly and it wouldn't be unreasonable to expect a suitable working quantum computer within 10 years. Moody explained, "Historically, it has taken a long time from deciding a cryptographic system is good until we actually get it out there as a disseminated standard in products on the market. It can take 10 to 20 years."

Wish them luck!