Today’s encryption algorithms threatened by a quantum leap
By Dzof Azmi April 25, 2018
- In the next year, a quantum processor will probably be shown to outperform supercomputers
- IBM and Google have announced such technologies; working demonstrations are anticipated
QUANTUM computing has long been known to be a nemesis to current encryption algorithms, but until now the best working versions are more akin to curious demonstrations than any real threat.
However, this may change very soon and people should start addressing the risks now, warned Joseph Fitzsimons, an Assistant Professor at Singapore University of Technology and Design and at the Centre for Quantum Technologies.
“I think for sure in the next twelve months or so we'll probably see the first demonstrations that perhaps a quantum processor has outperformed a classical supercomputer," he said during a forum about Quantum Computing at EmTech Asia 2018 held in Singapore.
"People should start to worry about their 'crypto trash'," further explained Fitzsimons, referring to archived data that may be secured with older, weaker encryption susceptible to quantum computers, even if one doesn't exist now.
"What happens if there is one in ten or fifteen years? Is there stuff that you need to keep secure beyond that time horizon?” he questioned. "By today that revolution has really started to happen."
The strange world of quantum computing
"(Quantum computers) can make use of more efficient algorithms that run faster and use fewer resources than classical computers," said Fitzsimons, whose simple explanation belies the complex world of subatomic physics.
Quantum computers take advantage of quantum mechanics, where atoms and particles interact with each other at the atomic and subatomic level. A quantum computer is simply a device that stores and manipulates data as quantum states - and is subject to their very unusual effects.
"It's really where all the power comes from but it's not really something we have an intuition for. It's not something we experience in our day-to-day lives."
One analogy would be to say that the difference between current and quantum computers is similar to the difference between convection and microwave ovens. Both can cook food, but do so in completely different ways. The technologies used are different, the methods employed are different and the kinds of recipes (algorithms) that are suitable can be completely different as well.
As another analogy, Fitzsimons talks about how the two different kinds of computers would try to find a lost object in a room. If you were using a conventional computer, you would give it a list of places where the object could be and ask it to check them one by one.
For quantum computing, you can do something completely different. "You try to create some kind of cancellation effect so that your chance of getting the wrong answer cancels out.” As strange or counterintuitive as this seems it’s something physicists have long observed but never quite satisfactorily explained to the layman.
"We can see quantum effects in the lab quite easily and we've a history of doing experiments in this that goes back a hundred years."
Factoring numbers and cracking encryption
An interesting quantum computing technique is something called Shor's algorithm, which was designed to factorise integers efficiently. "Many of the public key cryptosystems that are actually implemented at the moment are based on the hardness of factoring," elucidated Fitzsimons.
Using Shor's algorithm, the difficulty of breaking an encryption like RSA on a quantum computer becomes equivalent to using RSA legitimately on a classical computer - it other words, it's not difficult at all.
Shor's algorithm has been demonstrated to work on existing quantum computers, and in 2014 the number 56,143 was factorised - a very small number when compared to current public keys that go up to hundreds of digits (1024 bits).
However, the capacity and capabilities of quantum computers is increasing rapidly.
The size of quantum computers is measured in qubits (roughly analogous to a "bit" in conventional computing). "Twenty (qubits) you can simulate on your iPhone," explained Fitzsimons. "Once you get 50 (qubits), that process can no longer be simulated by a classical computer or even the largest supercomputers."
That day is almost here. In December 2017, IBM announced the development of a quantum computer capable of handling 50 qubits. Last March, Google one-upped and announced a 72-qubit square array quantum processor.
With current encryption techniques at risk, work is already underway to mitigate this threat. In 2016, the NSA released a prescient advisory saying that quantum-resistant encryption algorithms need to be developed.
The race is on. Fitzsimons identified countries like China and Australia as being two in the region that are investing heavily in quantum computing. Fitzsimons himself works at the Centre of Quantum Technologies which is based at the National University of Singapore (NUS).
“There is a lot of research (here) that relates to various problems related to building a scalable quantum computer," he said.
Unsurprisingly, Fitzsimons believes this rapid progress is likely to continue. "The doubling times of the number of qubits on the device has been roughly six months and that's across different devices made by different companies," said Fitzsimons. How long the quantum states are stable, another long-standing issue with quantum computers, has been also improving.
However, he is also anticipating that the results of any upcoming demonstrations will be fiercely debated, with much of it on the validity of the results. "I think there's probably going to be a year or two of back and forth on that kind of thing."