Quantum Computing's Threat to Public-key Cryptosystems

19.6.2017 securityweek Krypto
Quantum cryptography and Encryption Challenges

The Quantum Cryptography Problem

Fittingly, while we do know a little about 'what', we actually know little about 'where' (in time) we will get commercially viable quantum computers. The 'what' includes massively increased computational power. The 'when' is thought to be some time within the next 15 to 30 years.

When these two features are combined, we get the quantum cryptography problem: what are we going to do with current public-key encryption? Last year, scientists from Google and NASA suggested that D-Wave quantum technology could provide computing 100 million times faster than current conventional technology. This sort of power will 'break' current public-key cryptosystems.

As long ago as 1994, Peter Shor developed a quantum algorithm to factor large prime numbers. It was not considered an urgent problem at the time, given the lack of quantum computers. Today, however, quantum computing is much closer. If it becomes commercially viable within the next 15 years, then cryptography already has a problem -- the world's data currently protected by algorithms such as RSA, the world's most popular public-key cryptosystem, will become readable. If it takes nearer thirty years, then there is potentially time to solve the problem.

The problem arises from the length of time it takes to develop and test new cryptography, and then to re-tool existing infrastructures with the new quantum-resistant algorithms. The solution is for security to develop 'quantum-safe' public-key cryptography as soon as possible. It is not thought so pressing for symmetric crypto systems -- that problem can probably be solved by using larger keys for symmetric algorithms such as AES and Triple DES, and by using longer output from hash functions.

Last year NIST announced a new competition (PDF) to develop quantum-resistant public-key cryptography. It called for proposals in the Fall of 2016, with a deadline of November 30, 2017. It expects a 3-5-years analysis phase, with draft standards after a further two years. It announced that it would start to accept submissions on December 15, 2016.

One potential candidate was described by academics in France and Singapore on May 30, 2017 in a paper titled 'A New Public-Key Cryptosystem via Mersenne Numbers' (PDF). Mersenne numbers have long captured the imagination of mathematicians seeking an improvement to current public-key systems -- but not universally.

In 2009, Nathaniel Johnston, assistant professor at Mount Allison University, Canada, wrote, "Like all good myths, the Mersenne prime cryptography myth is so widespread because it is so close to being true." But the early interest in Mersenne numbers was that they could simply replace prime numbers with much larger prime numbers. This, according to Johnston, is the fallacy.

The new paper is different. "My comment was aimed at the idea that Mersenne primes can be used in RSA encryption (the 'standard' encryption scheme based on prime numbers), which is very false. However, [this paper] is about an entirely new encryption scheme that is built specifically around Mersenne numbers and Mersenne primes (and doesn't work with other primes). I have no reason to believe that there's any problem with this new scheme or its use of Mersenne numbers/primes."

The proposed new cryptosystem, says the paper, "is based on arithmetic modulo so called Mersenne numbers, i.e., numbers of the form p = 2^n - 1, where n is a prime." It does not necessarily require that n is a Mersenne prime, but prefers it. There is a known partial attack when n is not prime, but the paper adds, "we are not aware of any attacks even if p = 2^n - 1 for any large enough prime n. If we are willing to relax this requirement, then we can choose other values of n to get the desired security."

The paper describes theoretical attacks against its proposal, including lattice-based attacks, meet-in-the-middle attacks, and guess and win attacks. In general, it finds the theory stands up well; but less so for active attacks that ask for the decryption of incorrectly formed ciphertext and use the answers to recover information about the key. The authors' solution is to include "a transformation specifically designed for our bit-by-bit encryption."

"In this paper," the authors conclude, "we propose a simple new public-key encryption scheme. As with other public-key cryptosystems, the security of our cryptosystem relies on unproven assumptions... we mentioned some unsuccessful attempts we made at trying to break this scheme, and this led us to conjecture the security guarantee of our scheme." To verify their own conclusions, the authors urge other cryptographers "to try and find attacks on our scheme"; either conventional or quantum.

It may be that the results of any such feed-back will determine whether the authors will specifically submit their proposal to the NIST quantum-resistant competition before the November deadline. SecurityWeek has reached out to the authors to see if this is the plan, and will update this article with any response it receives. What is clear, however, is the increasingly urgent search for quantum-safe public-key cryptography is now in full swing.