Quantum computing timeline

Large quantum computers promise to solve many important problems currently beyond the reach of classical computers. They are best thought of as application specific accelerators that can solve a limited set of problems extremely quickly. One of their known features will be the ability to factor large numbers with a devastating impact on our global security systems which relied on this type of problem being difficult (RSA, D&H, and ECC). According to Prof. Johannes Buchmann, a respected post quantum cryptography expert who leads the Computer Science and Mathematics Department of Technische Universität Darmstadt (TUD): “This would be a nightmare for IT security.”

In 2004 there were already 155 quantum computing research projects in the public domain. In 2008 Andrew Shields, leader of the Quantum Information Group at Toshiba’s Cambridge Research Lab, is of the opinion that: “the use of quantum information technologies in business computing will become a reality in the next 10 years.” The quantum computing wild cats D-Wave have created great controversy with their claim that they will have quantum computer hardware and software services commercially available by 2010.

When do the experts say we might expect large code breaking quantum computers to arrive? In 2004 the Quantum Information Science and Technology Experts Panel of the U.S. Advanced Research and Development Activity (ARDA) under the auspices of the United States Army, Air Force, Navy, and the US National Science Foundation produced a lengthy Report with the conclusion that it might only be a decade or two before large quantum computers arrive (2014 to 2024).

Prof. Seth Lloyd was a co-inventor of the world’s first 2 qubit quantum computer and one of the ARDA Experts Panel. In May 2008 Prof Lloyd estimates that “at current rates of progress, big, code-breaking quantum computers are at least a decade away.” (2018).

There will always be sceptics

Even with the warning of these authorities, I have a few friends that remain sceptical. They observe that the progress towards a large quantum computer appears very slow and they wonder if they might never arrive. Their type of scepticism has always accompanied great advances, such as manned airflight/space flight and much more. Consider the widespread scepticism about the future capabilities of modern digital computers during their early development phase. We can see the same varying responses about quantum computers. The key point is that we already have quantum computers, they just need to grow in size. I have found it is useful to compare the historical development of modern digital computers and quantum computers. In the chart below we show the development timeline of semiconductors from the discovery of the PN Junction, and the timeline of quantum computers from the first proposal that quantum machines could do some operations faster than classical computers.

A logistics problem

One of the striking similarities between the two development timelines can be seen in the first 20 years where progress appears remarkably slow. It took the fledgling semiconductor industry 18 years after the first PN Junction to solve the logistics problem that would enable the semiconductor industry to aggressively scale in performance year after year.

It is interesting that in the first 13 years of development after the development of the first IC the number of low-cost transistors was the fastest, on average a chip doubled in the number of transistors every year. Today this rate of development has slightly reduced to doubling approximately every 2 years. The take home observation is that the initial limiting factor in the scaling of transistors was a logistics problem of finding a suitable technique that could scale. Today the development of quantum computing is at a similar stage to the first years of development of classical computing:

My colleagues at MIT and I have been building simple quantum computers and executing quantum algorithms since 1996, as have other scientists around the world. Quantum computers work as promised. If they can be scaled up, to thousands or tens of thousands of qubits from their current size of a dozen or so, watch out!”

The time it takes to search for a new cryptographic standard

If the ARDA Report Experts Panel is correct in their estimate of a possible arrival date after 2014, or Prof Lloyd is correct in his prediction on the arrival of large code breaking quantum computers after 2018, then this has serious implications given how long it takes to canvas, establish and deploy a new security standard. The post quantum crypto canvassing process is currently under way but there is no sign of a standardisation process. If we take the current US NIST SHA-3 hash competition as a reasonable guide then it could take six years from commencement to reach a conclusion on a new universal security standard for global Internet applications such as eCommerce IF ONE IS FOUND.

Now for key management purposes (key exchanges, digital signatures), against the RSA and the Diffie-Hellman and stuff (ECC), they flat-line under a quantum computer. It’s not just a cut the key size in half.
…
So this becomes an invitation to the research community to get cracking lads. We need new algorithms that are robust at least to the square root factor under a quantum computer attack that can be used for non-repudiation, and public key processes.  Open problem. Aching problem – work on it, please!

The time it can take to adopt a standard

There are two factors to consider in the adoption of a new standard. The will to do so, and the time required to implement once committed to adopting a new standard.

A example of the real-world delay by organisations to adopt new standards is illustrated in the continued use of the broken MD5 cryptographic hash function by some certificate authorities. The choice to delay in upgrading their services enabled rouge certificate authorities to be created (November 2008) which undermined the whole purpose of certificate authorities.

The implementation and deployment of a new security standard in important industries can take more than a decade. The European Eurocard, Mastercard Visa Co (EMVco) advises that "it will take 12 to 15 years for the infrastructure to be migrated in support of the new technique, which is why we are now conducting a review of various options."

So we are now 18 to 21 years into the future before a new post quantum secure banking standard may be in place even if a standardisation process for a suitable technology started today.

Encrypted data is being archieved

The kick is that most classically secured (encrypted) data is recorded and will continue to be recorded. The Internet and telephone systems allow interception and recording on a grand scale. ‘Blackhats’ (spies, disgruntled employees, political opponents, religious fanatics and others) inside your organisation may also have the ability to record this secured communications that the management may consider is safely silo’d away from the public domains. The fact that everything in the modern information society is interconnected and interdependent means that the weakest link enables attacks against critical infrastructure. The fact that security systems protecting important data are regularly made obsolete (such as superceded public key lengths) creates the incentive (like pension plans) for hackers inside and outside your organisation to record and archive secured data for later exploitation or auction. The ultimate buyer may be the party who first controls, or gains access to, a code breaking quantum computer. At this point virtually all recorded data becomes at risk and every system that relies on mainstream security loses all assurance of safe operation. Hence experts in academia, national security agencies and commerce describe the impacts in terms such as “nightmare” and "doom". Even if the first large quantum computer is owned by your allies it still has implications for national security and competitiveness.

Emerging solutions to solve the security threat based on symmetric techniques

Many groups within the cryptographic industry have been working hard to find a complete security solution. Just recently in October 2008 the University of Cincinnati (USA) held the second international workshop on post quantum cryptography (PQ2008). One of the four most promising areas of research studied at this conference is to find key exchange and digital signature technologies that rely on “symmetric” primitives for their security.

Modern standards based symmetric primitives include block ciphers and stream ciphers (which are used for achieving data privacy) and hash functions (which are used to provide ensure data integrity). Some of the existing standards based symmetric primitives are widely accepted by the security industry to offer excellent security against conventional and quantum computing attacks. This makes them good candidates for building post quantum secure digital signatures and key exchanges.

Digital signatures based on hash functions (Lamport-Diffie-Merkle schemes) were invented at roughly the same time of RSA digital signatures which are ubiquitously used today. Companies such as TUD and Hitachi have been offering highly efficient digital signature schemes based on this 30 year old technology since 2005. These schemes have been widely accepted as secure.

Symmetric key exchanges based on block ciphers and hash functions have been known for 30 years but had some practical real-world limitations with the number of users they could support in a single system. Today Synaptic Laboratories Limited has solved this problem allowing billions of users within one system that is collectively managed by different countries. Synaptic Labs' scalable symmetric key exchange solution has received positive preliminary evaluations by academic and corporate cryptographers in 2008. Further refinements to broaden the range of potential applications are now nearing completion.

Together Synaptic’s key exchange and TUD’s digital signature technologies built using standards based symmetric techniques can wrap around and protect mainstream key exchanges and digital signatures from quantum computing attacks. What this means is that existing users and vendors of mainstream PKI solutions can continue to use the classically trusted technologies while relying on Synaptic and TUD technologies to provide protection in the quantum future.

Synaptic welcomes enquiries from users and industry prior to publication of Synaptic technologies.

Click here to learn more about the business logic behind Synaptic Labs' suite of security technologies.

Click here to learn more about the Synaptic Labs' post quantum secure key exchange technologies. Synaptic Labs' technologies are an advance on symmetric cryptographic techniques used in earlier standards-based key exchange technologies that pre-date public key technologies.