Quantum leap in cryptography

Some 25-odd years ago, computer scientists started worrying about the Y2K problem. For the benefit of young readers, computer programmers used to save storage space on hard drives by using dating systems that ran only the last two digits of the year. That code was embedded on millions of systems, ranging from home PCs, to power-grids, and machines controlling nuclear missiles.
 
Nobody knew how that code would behave, or misbehave, once “1/1/00” was hit. It took an enormous effort to sort out potential chaos, checking, and rewriting code, line by line. Fixing Y2K cost over $500 billion. The Indian IT industry was a prime beneficiary since it had the labour to do this tedious task.
 
Computer scientists are now worrying about the Y2Q problem though nobody is clear as to timelines. Y2Q equates to “Year to Quantum” — the point at which quantum computers become stable devices. In the jargon, “quantum supremacy” would be a practical demonstration that quantum computers could outperform conventional machines. There are hundreds of research programmes around the world hell-bent on achieving this.
 
In theoretical terms, q-computing is magnitudes more powerful than conventional computing. A normal computer uses binary bits set to either “1” or “0”. A quantum computer uses “qubits”, which exploit quantum superposition to be both 1 and 0 at the same time. So while two bits represent only two numbers and 10 bits represent just 10 numbers, two qubits represent four numbers and 10 qubits can represent 1024 numbers.
 
In theory, a Quantum machine that handled 50 qubits could out-calculate the fastest super-computers. In practice, superpositions collapse all the time with attendant loss of information. Researchers have broken their heads trying to design stable qubit formations.
 
A researcher from Google claims that it will have demonstrated “quantum supremacy” by end-2017.
 
Charles Neill at the University of California Santa Barbara and Pedram Roushan at Google have put together a system that runs currents in both directions through a superconducting loop of metal at very low temperatures. They claim 9 qubit stability with this superconductor loop. They may be able to scale up to 60 qubits. If they do, Y2Q will be a gigantic step closer.
 
Once Y2Q is here, a mega-effort will be required to upgrade global cryptography standards. Digital cryptography currently depends on elementally simple mathematical logic. It is easier to multiply numbers than to divide numbers into their factors.
 
Multiplication is a mechanical process even if it’s laborious to multiply large numbers, digit by digit. Division is much more difficult. Another way of looking at it: Multiplying involves taking two known numbers and generating a third by multiplying known digit by known digit. Division involves taking one known number and extracting an unknown number of unknown factors.
 
If the number is a large prime number, the mechanics involve dividing it by every number that is at least half as large, one-third as large, one-fourth as large, one-fifth as large, etc, one-sixth, etc., until you establish it is prime. This can take very powerful computers thousands of years to accomplish if the number is very large. Clever computational tricks can shorten this process but not by very much.
 
Most commercial cryptography systems take two very large prime numbers and multiply them together to generate a semi-prime (a number with only three factors, including 1). That semi-prime has to be split into its factors in order to break encryption. Military encryption systems use even larger numbers. The assumption: No cracker will have the computer resources and the time. Most nations try to ban encryption of above certain levels, or arm-twist manufacturers into setting back-doors because of this computational limit.
 
Quantum computing smashes that paradigm: Reliable qubit computers, running in parallel if required, can divide numbers exponentially quicker. Every sort of device and system imaginable from your smartphone to Amazon’s back-end, to Visa, Aadhaar, to clouds, and nuclear weapons control systems, uses cryptography that is vulnerable if the calculations can be speeded up.
 
As Y2Q becomes reality, there will be a mega-opportunity to create quantum-safe encryption systems along with new standards, laws, etc. Will India’s IT industry and mathematicians be able to fill that need? Somehow I doubt it.

Twitter: @devangshudatta