Nobody was too worried. A quantum computer capable of running Shor's algorithm seemed so distant. In 2001, there was a breakthrough, of sorts. IBM researchersworking on an early model of a quantum computer used Shor's method to calculate the factors of 15. Eleven years later a bigger number was factored: 21.
Up against the recommended RSA key length of 3072-bit or longer, the quantum effort so far seems feeble. But the advent of a far more powerful machine is getting closer by the day. The likes of Google, NASA, Lockheed Martin, Commonwealth Bank and Telstra are backing bids in a global race to build one first.
"Although we don't know exactly when they're going to come," says QuintessenceLabs' Leiseboer, "we do know, when they do come, that everything that's processed today will be made vulnerable at that point in time. Any information that has longevity now is already an issue."
Even tougher maths
To avoid such an event - which has been dubbed "wiki-leaks on steroids" and the "cryptopocalypse" - there is a scramble to come up with a new suite of algorithms that are "quantum-resistant".
Some, the "lattice-based cryptographic primitives" proposed by researchers at Microsoft, though promising have not yet been formally proved safe.
The US National Security Agency, meanwhile, is pushing the National Institute of Standards and Technology and the wider community to develop a "widely accepted, standardised set" of resistant algorithms, but at best these will be available sometime "in the next decade".
ETSI, the European Telecommunications Standards Institute, set up the Quantum Safe Cryptography working group last year. "We want to be ready" said its chairman Mark Pecan. Quantum computers, he added, were a "significant threat to our global information infrastructure".
Google, meanwhile, are testing a "post-quantum algorithm" called New Hope, testing it with some users via Chrome Canary.
But quantum-resistant algorithms are currently just that - a hope. Google admits that its "might turn out to be breakable even with today's computers". And even when a potential solution is found - standardisation takes significant time and testing. Failed attempts litter the course.
In 2013, the UK's Government Communications Headquarters (GCHQ) abandoned years of work into what they hoped would be a quantum resistant, cyclic-lattice based primitive - code named Soliloquy - after managing to crack it with a 'reasonably efficient quantum attack'.
In a paper titled 'A Cautionary Tale' GCHQ's experts warned that "much care and patience" is required to apply a thorough security assessment.Their conclusion was frank: "designing quantum-resistant cryptography is a difficult task".
Sign up for MIS Asia eNewsletters.