Understanding the Risk Impact and Threats of Quantum Computing on Cryptography and Cybersecurity

_{Joe Ghalbouni – Head of Risk, Quantum Strategy Institute}

Business leaders thinking about the future of their companies’ data security need only to look at the image attached to this article. A key with the potential to open the universe of digital 1’s and 0’s. The abundant research and development being applied to quantum computing promises to launch a whole new universe of computing security considerations. In this article, Joe Ghalbouni provides insight into what quantum computing is, quantum cryptography (and post-quantum cryptography) and when business leaders need to be thinking about this priority subject.

What is quantum computing?

Quantum computing has been at the heart of academic research, since its idea was first proposed by Richard Feynman, in order to understand and simulate quantum mechanical systems efficiently. The main idea is to make use of a quantum mechanical system in order to perform calculations. Since this system obeys the laws of quantum mechanics, it allows for an accurate simulation of a quantum system, the latter which can only be simulated classically up to a certain error factor.

Beyond this perspective, making use of purely quantum phenomena such as superposition of states, quantum parallelism and entanglement, leverage a computational potential which can allows us, for particular problems, to compute much faster. We are speaking here of orders of magnitude! The quantum bit, most commonly referred to as qubit, is the analogous of the classical bit for quantum computers. Unlike its classical counterpart, it’s not bounded to the states 0 or 1. It can be found in a superposition of both. This permits for the computing power of a quantum system to grow exponentially, each time a new qubit is added.

Among the mathematically complex problems a quantum computer promises to solve more efficiently, we denote those on which cryptographic security is solely based. Quantum computers thus are an imminent threat to currently employed cryptography protocols. But how can we address this risk and opt for a mitigation solution? Let’s start with a review on cryptography.

Reviewing cryptography

Classical cryptography as currently referred to in the quantum ecosystem, is based on the mathematical complexity to break encryption. While there are numerous cryptography protocols, they can be classified into three categories:

• Asymmetric cryptography: each user holds what is commonly referred to as a public and a private key. For example, the public key of a user A, as its name suggests is available for everyone who wants to send an encrypted message to that particular user. By using his/her public key, other users on the network encrypt a message and send it to user A. The private key as its name suggests is private to the user A, and enables him/her to decrypt the encrypted message. The public key is created from the private key, and is equivalent to a product of prime numbers. The reverse process consisting of factorizing this number, in order to retrieve its primes, and thus deducing the private key from the public key, is considered a hard to compute problem. Notable algorithms include RSA, ECDSA, Diffie-Hellman, etc.

• Symmetric cryptography: each user holds a private key used for both encryption and decryption. In order for two users A and B to securely interact, a key must be agreed upon prior to message encryption and exchange. This key has to be transferred in a secure manner to avoid any eavesdropping. Guessing a private key requires to go through trials and therefore, no method is more efficient than brute force. Notable algorithms include AES, Blowfish, DES, etc.

• Hashing functions: a string input comprising a random number of characters, passes through a hashing function and comes out as an output of a fixed number of characters. This function is mathematically irreversible. A specific input, will always give the same output once it passes through the same hashing function, ensuring that we can verify that it matches when comparing to a database. Notable algorithms include SHA-2, SHA-3, MDA, etc.

Quantum Computers and the threat on Cryptography and Data

Quantum computers are believed to be more efficient than their classical counterparts at solving specific problems. Notable quantum algorithms such as Shor’s factoring algorithm and Grover’s search algorithm raise serious concerns towards current digital cryptography protocols. But how are these protocols exactly affected and what products are they tied to?

• Protocols related to online banking and digital signatures: asymmetric cryptography for example, becomes very vulnerable. Shor’s algorithm allows for an efficient factorization by finding the primes that form a number. This means that private keys will be easily deduced from public keys and therefore encryption will no longer be secured. This is a main concern for RSA and ECDSA. Online banking transactions will become at risk, as well as digital signatures such as those used in cryptocurrency to verify transaction ownership. It is believed according to recent scientific articles that Shor’s algorithm will efficiently break RSA-2048 and ECDSA-160 for a respective quantum processor of 4096 qubits and 1000 qubits [1-3].
• Protocols related to data and servers: symmetric cryptography will see its security level drop. Grover’s algorithm results in a more efficient search optimization than any known classical search algorithm, and can considerable reduce brute force attempts from  on average, to  (  being the possibilities). Thus in the case of AES-128, where 2¹²⁸ key combinations exist, it would take Grover’s algorithm 2⁶⁴ operations to find it instead of 2¹²⁸/2 classically. This means a 50% speed gain. This endangers any data encrypted and stored on online servers, especially if it remains of significance importance over time [1-3].
• Protocols related to blockchain and cryptocurrency: hashing functions being irreversible, mean that quantum computers will not bring any advances towards decrypting them. It is simply not feasible. However, collision and birthday surprise attacks which rely on trial of a big set, similarly to brute force methods, will become more powerful thanks to Grover’s algorithm. The speed up attainable in the search algorithm will make it easier to find the right input for a given hash function’s output. For example, SHA-256 which maps an output of 256 bits, imply 2²⁵⁶ possibilities requiring classically on average 2²⁵⁶/2 trials to find the right combination. Grover’s algorithm will reduce this to  trials [1-3]. This indicated a 50% speedup. While it’s still a big number, it reduces the bit security level to half of its original value and is something to keep in mind. Hashing functions are extensively used in cryptocurrencies and any vulnerability that can target the blocks in the public ledger, needs to be addressed. Although, when dealing with a distributed ledger, any modification in the block can be corrected right away by the majority of the nodes.    

Quantum Computing Timeline

What about the timeline? How much time do we still have to become prepared? Although universal quantum computers that can run these powerful algorithms, and that comprise inherently stabilized qubits might take a couple of decades to see the light, it still is a short period of time. Being quantum ready requires training of personnel at different levels (top managers, IT, HR,…) as well as recruiting the right people for the right positions.

The quantum ecosystem is constantly evolving and maturing, and following the latest advances is crucial in order to invest both time and money in the right place and at the right moment. Also, quantum algorithms are constantly being developed and only require those universal quantum computers to be put to the final test. Simulators allow us already to fully understand for a few qubits how they work. Scaling an algorithm to a bigger number of qubits is, most of the time, pretty straight forward. Once available on the market, fault tolerant quantum computers can be operational right away.

Mitigation (Post-Quantum and Quantum Cryptography)

On the technical practicality, what should businesses do?

Businesses must assess the risk present on their data and cybersecurity by quantum experts. The reports will indicate how safe the system is and for which estimated period of time. From there, companies will have to put in place a long term strategy to go towards one of two solutions, or a mix between them: quantum proof algorithms or purely quantum protocols.

Quantum proof algorithms saw the light after the National Institute of Standards and Technologies (NIST) launched an ongoing competition to pick a newly designed quantum safe encryption protocol. At the moment of writing this article, NIST has reached the final phase and recently released an FAQ about Quantum Computing and Cryptography [6].

With quantum algorithms constantly being developed, these quantum proof algorithms might become obsolete one day. Thus, quantum cryptography which makes use of quantum phenomena for intrinsic security and which allow us to detect the presence of an eavesdropper, might be a more appropriate and safer solution. Quantum Key Distribution (QKD) allows for a provably quantum secure scheme of private key exchange. Not only do we get over the idea of a public/private key combination, but private keys will be exchanged remotely, the latter requiring however an appropriate quantum architecture based either on optical fibers and/or satellites.

A hybrid solution could consist of injecting pure quantum randomness instead of classical pseudo-randomness when generating keys for RSA and ECDSA, or when generating passwords. When a list of those is generated all at once, it is possible for an attacker to guess the underlying function behind the pseudo-randomness and from a few elements at their disposal, figure out the whole list. Adding quantum randomness through quantum random number generators, is a good solution since quantum is intrinsically random with its measurement process.

IdQuantique is an example of a Swiss company that proposes QRNG and QKD ready solutions for implementation. We also denote similar products proposed by the Canadian and American companies evolutionQ and QuintessenceLabs.

Conclusion

Getting prepared to face the and benefit from the second Quantum revolution is a challenge. However, when well prepared, businesses can explore so many new opportunities, allowing them to fully embrace this new technology. Whether it is through correctly assessing every risk associated with Quantum Computing, on the company’s different levels, or through its change in managerial approach, businesses should start addressing the Quantum question right away, before it becomes too late!

Joe Ghalbouni is Head of Risk of the Quantum Strategy Institute and Co-Founder & CTO of Quantum Risk Advisory, having been an Associate Professor of Physics, Lecturer and Researcher in Quantum Computing Information & Communication since 2013.

References

• [1] V. Mavroeidis et.al., “The Impact of Quantum Computing on Present Cryptography”, IJACSA Vol.9, No. 3, 2018
• [2] Z. Kirsch, “Quantum Computing: The Risk to Existing Encryption Methods”, Tufts University, 2015
• [3] W. Easttom, Chapter: “Quantum Computing and Cryptography”, Book: “Modern Cryptography”, Springer, 2020
• [4] I. Faro, “IBM’s roadmap for building an open quantum software ecosystem”, 2021
• [6] M. Swayne, “NSA Releases Quantum Computing, Post-Quantum Cryptography FAQs”, The Quantum Daily, August 2021
• [7] “Mastering Strategic Management”, University of Minnesota, 2016
• [8] A. Hax, “The Strategic Management Frameworks”, MIT Sloan School of Management, 2006
• [9] “Why Strategies Fail”, Strataegos Consulting, 2014
• [10] A. Dunne and F. Raby, “Speculative Everything”, 2013

Copyright 2021 Joe Ghalbouni