Post-Quantum Cryptography: does bulletproof cryptography still exist?
Author: Gašper Grad
Source: Fintech Factoy
Quantum computers are being developed rapidly. This autumn Google claimed that for the first time in the history their quantum computer has beaten the strongest classical computer when solving a specific task. That is a reason for excitement but also for concerns about internet security. Today, we are surrounded by cryptography as never before. It is used for digital communications, banking etc. All cryptography is based on mathematical problems that are extremely demanding for classical supercomputers, but they might not be that demanding for quantum computers. That is why the security of today’s encryption and even blockchain has to be called into question. Does quantum-safe technology exist?
Welcome to quantum space
Quantum computers are machines that perform operations exploiting the laws of quantum mechanics, the branch of physics dedicated to the smallest particles and waves. Quantum computing began in the 1980s when quantum mechanical model of a computer was described. Since then the technology has developed rapidly. It seems that in a few years quantum computers will be able to solve some real-life problems that today’s supercomputers cannot cope with.
Whereas classical computers store information on bits (that can represent either 0 or 1), quantum computers use quantum bits or so-called qubits. The qubits can take advantage of quantum superposition and represent 0 and 1 at the same time. Furthermore, while bits work independently, qubits are entangled with each other. When we add one bit to a classical computer, the number of possible combinations rises by the number of existing bits. In contrast, adding one qubit to a quantum computer, increases the number of possible combinations by 2^number of qubits. In other words, while classical computer capacity is growing linearly, the quantum computer’s capacity is growing exponentially. That is the reason for the hype.
At first, quantum computers are expected to make the biggest impact in the field of pharmacy and chemistry. Following this, they might have an impact on finance, meteorology, energetics, transport, logistics, artificial intelligence, machine learning, and all kinds of optimizations and simulations. Boston Consulting Group (BCG) predicts that by 2050, quantum computers will contribute 450 to 850 billion USD to operating income of their users in the form of lower costs and additional revenues. When established, the market is expected to be worth 260 billion USD. In comparison, the market of ‘normal computers’ is currently worth 800 billion USD.
“Quantum supremacy”: beating supercomputers
On 20 September 2019, NASA (presumably) accidentally published a scientific paper, explaining that they have achieved quantum supremacy in cooperation with Google. The company has confirmed the news on 23 October 2019. Quantum supremacy means that a quantum computer outperforms a classical one. Google argues that their 53 qubit computer named Sycamore has presented the probability distribution of a 53 digit pattern of 0 and 1 in only 300 seconds. According to their calculations, the world’s best supercomputer named Summit, which has the size of two tennis courts, would need 10,000 years to tackle this problem.
Following this, quantum supremacy became a hot topic. The International Business Machines Corporation (IBM) claimed that Summit could tackle the challenge in “only” 2.5 days, which is still 1,200 times longer than the time needed by Sycamore. Moreover, others pointed out that the problem was designed for quantum computers and quantum supremacy. Therefore, this experiment cannot be applied to solving real-life problems. At least for now. Nevertheless, it is a fact that a huge progress has been made. And sooner or later, quantum computers will be able to solve real-life problems more efficiently than classical computers. Besides solving real-life problems quantum computers could also cause some huge problems.
“Day zero” for cryptography?
The entire internet security relies on encryption of two types: symmetric and asymmetric. Whereas symmetric encryption uses only a secret key, asymmetric encryption uses a combination of a public and a private key. Most of the popular algorithms rely on integer factorization problem, discrete algorithm problem and elliptic-curve discrete logarithm problem. Those problems are extremely demanding for classical computers, but not for a large scale quantum computer.
By using a quantum computer running Shor’s and Grover’s algorithm respectively, the most commonly used security algorithms, such as RSA, ECC, Diffie-Hellman and AES, could be cracked. In other words, the systems’ security should be upgraded before large scale quantum computers become reality. There is also a threat that sensitive data could be captured today and decrypted in the future.
The question is whether someone can secretly develop a large scale quantum computer. It is possible that this has already happened. Anyway, most of the experts agree that the chances of secretly developing a large scale quantum computer are extremely low due to the complexity of the project. And even if somebody has it, it is questionable in what scenario would they reveal themselves and misuse the machine.
Quantum resistant cryptography: myth or reality?
Governments (e.g. the US, China) consider quantum computing to be one of the top national security priorities. The development of quantum computers goes hand in hand with the development of quantum-resistant encryption i.e. cryptography that can not be cracked by quantum computer, also known as post-quantum cryptography (PQC) or quantum-resistant cryptography. Research institutes, universities, large corporations and plenty of start-ups are searching for the best way to protect information against attacks by quantum computers.
It was clear since the beginning of the 21st century that new ways of encryption would be needed. In 2006, the first PQCrypto conference took place in Belgium. In april 2020, it will be organized for the 11th time. The venue will be in Paris. In the last 5 years national and international institutions have started to work towards post quantum standards. In 2015, European Telecommunications Standards Institute (ETSI) published a white paper, urging all the stakeholders to investigate and ultimately implement some kind of quantum resistant cryptography. North American National Institute of Standards and Technology (NIST) has opened a call for quantum-resistant algorithms, and received 69 applications. In January 2019, they introduced the shortlist of 26 best solutions. They include 17 algorithms for public key encryption and 9 digital signature algorithms.
The world’s largest association of technical professionals Institute of Electrical and Electronics Engineers (IEEE) and Accredited Standards Committee (ASC) X9, which is in charge of US financial industry standards, have already specified standards for quantum-safe public key cryptography. ETSI and NIST have both issued reports on post-quantum cryptography and are expected to establish standards in the next couple of years.
Even though standards are not clear yet, some organisations are already implementing PQC for the most valuable information in their systems. Most organisations are expected to adopt PQC once the institutions like NIST and ETSI establish the new standards. According to the survey from 2018 by Cloud Security Alliance, 86% of the IT managers were aware of the threat by quantum computers and 20% believed that they should implement PQC in the next 12 months.
The largest market for post-quantum algorithms will be web browsers. Financial sector is also at high risk. Cryptocurrencies like Bitcoin and Etherium that rely on the use of public keys will have to change to PQC. A company that is entirely dedicated to analysing quantum computing sector Inside Quantum Technology has predicted that the market for post-quantum cryptography software and devices will be worth $3.9 billion by 2028. Once large scale quantum computers are developed, it is expected to start growing rapidly.
This encourages private sector to get involved. Some of the most outstanding projects so far include an online open source library of quantum safe algorithms called Open Quantum Safe developed by Microsoft, quantum-resistant cryptocurrencies e.g. QRL, Praxxis, and Mochimo and quantum-safe blockchain e.g. QAN and Nexus blockchain.
Cryptography is the crucial element of digital age’s security. Quantum computers are setting up new rules of the game. The world is getting ready but it is not clear what quantum computers will be capable of. Thus, we cannot know for sure whether “quantum resistant” solutions are really what they say they are until large scale quantum computers become reality.