Special Report by Jane Lo, Singapore Correspondent
Around the world, governments and companies are racing to build quantum computers that will render many of today’s cryptographic systems insecure.
Many cryptographic protocols today are based on difficulty of decomposing large integers into smaller ones, otherwise known as “factoring”. No known efficient algorithms exists. Instead, breaking a key means performing an exhaustive search using classical computers which are incapable of solving fast enough. It is this “speed” bottleneck that is at the heart of many cryptographic algorithms behind the public-key infrastructure.
But with powerful non-classical computers, factoring or “reverse-engineering” the keys is no longer perceived as a mere theoretical discussion.
Dr Alexander Ling (Principal Investigator at the Centre for Quantum Technologies, associate professor at the NUS, theme leader at the NUS-Singtel Cyber Security Research & Development laboratory) wrote in The Straits Times [June 17, 2017], that “quantum computers should bring benefits in areas such as optimization and drug simulation but it is also an established fact that they can crack today’s encryption systems”.
What is Quantum Computing?
Quantum computers exploit quantum mechanical phenomena.
Dr Joseph Fitzsimons, Principal Investigator, Centre for Quantum Technologies, National University of Singapore and Associate Professor, Singapore University of Technology and Design, Singapore. Presenting at Quantum Technologies @ IoT Asia 2018 Singapore EXPO Photo Credit: IoT Asia 2018.
In contrast to conventional computers, quantum computers are based on qubits instead of bits as the smallest memory unit. A Qubit can take on a multitude of states – different than a bit.
According to theoretical studies, quantum computers will be able to solve certain problems in much less time than conventional computers, using quantum algorithms such as Shor and Grover.
This ability to factor at speeds would compromise the confidentiality and integrity of digital communications built on Public Key Infrastructure running today’s cryptographical protocols.
Quantum-safe Cryptosystems
Christian Kurtsiefer, Professor, Centre for Quantum Technologies. Presenting at Quantum Technologies @ IoT Asia 2018 Singapore EXPO. Photo Credit: IoT Asia 2018.
While today’s small quantum computers are not a risk, the industry is moving fast – companies including IBM and Google are rapidly increasing the size of their machines.
The interest is now focused on designing the next generation of cryptosystems which are immune to quantum attacks, or quantum-safe cryptographic systems, to ensure future-proof data protection.
There are two approaches – a search for mathematical problems that will remain difficult for a quantum computer and developing quantum hardware for encryption.
The goal is to develop cryptographic systems that are secure against both quantum and classical computers – and can interoperate with existing communications protocols and networks.
Searching for quantum safe mathematical problem
US National Institute of Standards and Technology (NIST) has begun a process to define “post-quantum” standards for cryptography, with a call for proposals for cryptographic protocols resistant to attack by quantum computer.
Accepted into round one of the competition was a proposal from CQT researchers (Divesh Aggarwal, Miklos Santha and Anupam Prakash), with collaborator at the UPMC University of Paris (Antoine Joux).
The team invented a new key encapsulation mechanism convertible into an encryption system based on a specific prime number for an arithmetic modulo Mersenne number.
It will take some time and analysis before NIST reports its findings, and then a further couple of years for the agency to have ready draft standards. The agency does not expect to pick a winner, but to identify several algorithms as “good choices”. The goal is to recommend approaches for quantum-resistant encryption early enough to protect data that needs long-term security, overlapping with the possible timeline for the arrival of large-scale quantum computers.
Developing hardware – QKD
Arguably “hackability” can be mitigated with a larger key size, provided that keys are distributed with maximum security. So, how can key negotiation protocols (short of a physical transport) be designed to ensure that only trusted parties have them – that no eavesdropper has copied the key during its distribution?
“Quantum phenomena are very fragile. As soon as the particles start interacting with other particles in the environment, the quantum particles wash out and lapse into classical behaviour. This means to use these particles you have to isolate them well, on a micro level, and on top of that you have to stabilise the system. It’s terribly difficult but it is possible. What are our chances of building one? It’s still speculation but the progress is actually quite remarkable. Interest in this area has accelerated in the last few years. The likes of Google and IBM are building quantum computers” – Artur Ekert , Director of the Centre for Quantum Technologies (CQT), in interview with Jan-Peter Westad, tankmagazine. Source: Networked Quantum Information Technologies NQIT. UK National Quantum Technologies Programme. The Commercial Prospects for Quantum Computing. Issue 1, December 2016.
While quantum computers which are likely to break encryption and reverse-engineer keys are still at the early stages of research, there are already working prototypes of QKD, or Quantum Key Distribution.
QKD allows two distant users, who do not share a long secret key initially, to produce a common, random string of secret bits, called a secret key. Using the one-time pad encryption this key is proven to be secure to encrypt (and decrypt) a message, which can then be transmitted over a standard communication channel.
Generation one QKD – Single-photon technology BB84 – had already been demonstrated in test-case scenarios such as online voting and bank transfers, where commercial suppliers include Quintessence, QuantumCTek.
This technology exploits properties of photons (particles that transmit light) to transmit data for secure sharing of a key between a sender and a receiver. To steal the key would require knowing the photon properties – which due to quantum physics law, is impossible without changing the properties’ behavior and alerting both trusted parties to the attempted hack.
While the key lacks today’s mathematical structure for the quantum computer to analyse and break, the fragile nature of the phenomena makes it hard to work over long distances. The best optical fibers can carry these photons to around 200 kilometers before light absorption makes the process impossible.
An advanced form of QKD achieves this with quantum entanglement. This was demonstrated at CQT over fiber and free-space, including daylight operation.
Entanglement, whereby two particles behave like one regardless of distance apart, strengthens the security of QKD over long distances. The security is derived from “monogamy of quantum entanglement” – if two particles are fully entangled they cannot be entangled by any other particle. Measurement result of a perfect correlation could form the basis for building a secret key.
One example of these QKD methods was illustrated in a report by researchers in January 2018 using the satellite nicknamed “Micius” after an ancient Chinese philosopher. Through satellite-to-ground secure key distribution, a secret key was created between China and Austria at locations some 7,600 km away from each other. During the experiment, scientists transmitted images between the two countries, and a 75-minute video conference was successfully held between Beijing and Vienna.
Singapore’s Centre for Quantum Technologies
CQT’s Alexander Ling and Singtel’s Amelia Tan presented a demonstration of quantum key distribution to Singapore Deputy Prime Minister Mr Teo Chee Hean and other guests at the launch of the NUS-Singtel Cyber Security Research and Development Laboratory. An international team including CQT’s Alexander Glaetzle has proposed a new quantum technology to help in transferring information from light to matter. It could find applications in networking and quantum computing. Photo Credit: Centre for Quantum Technologies
Singapore’s Centre for Quantum Technologies is prominent in setting the agenda of and leading worldwide research efforts in the field of quantum cryptography and quantum algorithms. The Director of CQT, Artur Ekert, invented the idea of using entangled particles for cryptography proposed the QKD method based on quantum entanglement.
Other notable ongoing research projects of the Centre include:
- S-Fifteen, a spin-off from the Centre for Quantum Technologies to commercialize proprietary quantum cryptography technologies developed over decades of research
- CQT scientists are participating in the NUS-Singtel Cyber Security R&D Lab to prepare local optical fibre for QKD technology, aimed at securing critical infrastructure and sensitive communications. Launched in October 2016, the lab aims to develop novel data analytic techniques to detect and respond to security attacks and to come up with new approaches to IT systems that are ‘secure by design’. Some of the projects include: fibre-compatible quantum signal generator, and delivering quantum signals over Singtel’s fiber network.
Entanglement – Satellite launch
SpooQy Sat, held in the picture by satellite expert and CQT Senior Research Fellow Robert Bedington. Cubesats are built from units measuring 10cm along each edge. SpooQySat is made of three such cubes. Photo Credit: Centre for Quantum Technologies
In December 2015, NUS launched the 2U CubeSat Galassia, which carried the first demonstration of CQT’s SPEQS (Small Photon-Entangling Quantum System), a system designed in collaboration with the University of Strathclyde.
The CubeSat demonstrated the first instance of generating correlated photons – a precursor to creating entangled photons- in space, and the results were published in May 2016.
The goal of SPEQS, however, had always been to generate fully entangled photons.
Alexander Ling, Principal Investigator at CQT, explains why:
“We are taking a step-wise approach to building quantum satellites for long-range quantum communication. To achieve global coverage will eventually require a constellation of satellites. We are working with the CubeSat standard to develop compact and cost-effective technology. Our first tests validated our design for a rugged source of correlated photons. Our next satellite will create entangled photons, and we will be building collaborations for the next step of satellite to ground transmission.”
And what does it mean for Crypto Currency?
Miklos Santha (left) and Troy Lee (right), Principal Investigators at CQT, and their collaborators are providing advice on the quantum security of cryptocurrencies. Photo Credit: Centre for Quantum Technologies
In a white paper, (Miklos Santha and Troy Lee, Principal Investigators at CQT, and collaborators Gavin Brennen, Macquarie University and Marco Tomamichel, University of Technology Sydney) estimated the speed of the quantum algorithms and project developments in quantum computing technology, to put a timeline on when cryptocurrencies could become insecure.
Signature scheme
They warned that the signature scheme, which verifies Bitcoin’s ownership, could be broken within a decade.
The Bitcoin signature scheme is based on ‘elliptic curve’ cryptography. On a sufficiently large quantum computer, Shor’s quantum algorithm could compute the secret key corresponding to a given public key very quickly. If a signature is cracked, the hacker can spend the coins, stealing them from the rightful owner. However, this is at least a decade away.
“The main quantum bottleneck is having a quantum computer with enough qubits to run Shor’s algorithm on the scheme used by Bitcoin. We estimate it would take about 500 thousand to 1 million qubits. By the most optimistic estimates, in 10 years the signature scheme of Bitcoin could be cracked in under 10 minutes by a quantum computer,” explains Troy. Other cryptocurrencies that use similar security schemes will be vulnerable, too.
Proof-of-Work
The team also analysed the ‘proof-of-work’ used to record Bitcoin transactions.
As Grover’s quantum algorithm is proven to be able to perform this search with quadratically fewer queries than needed classically, it seems to imply quantum dominance in bitcoin mining.
However, current specialised mining devices, called ASICs, can perform 14 trillion search queries per second, which is a massive gap compared to the near-term quantum devices at 100 million operations per second, essentially negating the quantum speedup achieved by Grover’s algorithm.
Bitcoin’s Proof-of-Work, concluded the team, is unlikely to be vulnerable to quantum computers in the near future.
