How to improve cybersecurity through quantum technology ?
In 1977, an article in Scientific American stated that it would take 40 quadrillion years to crack a message encrypted with one of the most secure protocols called RSA-129. In fact, twenty years later and within six months the code was cracked using a distributed network of computers.
In parallel to the progres of “Classical” encryption methods, physicists, mathematicians and engineers have worked on new concepts. Devices have emerged that use the principles of Quantum Physics, and powerful and sophisticated mathematics to communicate safely with respect to any kind of attack, classical or quantum. Why ? Because, until proven otherwise, Quantum Physics is a complete description of the world and, thanks to modern technology, we can at last make the best of its extraordinary features.
More precisely, quantum technologies and mathematics are used to face the threat that emerging Quantum Computers pose for cybersecurity. Quantum Computers will be able to run ultra-complex models and solve extremely hard mathematical problems. And they will also be able to endanger most current and convenient encryption methods because of this previously unimaginable power. That will not happen tomorrow, because the machines needed to break encryption are insanely large from today’s perspective. But it is a serious enough threat that NIST, the US based certification body, has launched a call for propositions for so called “quantum safe” encryption algorithms to be implemented in the next decade.
This move has been triggered in part by a statement by the NSA in 2015 that surprised the whole community: “for those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition”.
The thinking is: given the time it takes to implement a new standard, 5 to 10 years at least, better to be safe than sorry and do the right think from the start. After all, the day a powerful enough Quantum Computer is available, it might not be made public, and a malicious hacker will be able to read ALL the data that has been encrypted with “old” methods like an open book.
Cryptocalypse ? Well, maybe not …
There are already commercial technologies that can protect against the threat posed by very powerful machines such as Quantum Computers. They increase substantially the level of security but it’s not a panacea. In practice, real life introduces imperfections in hardware that reduce the level of safety. And algorithmic solutions are safe only until proven overwise by hackers…
Let’s dig into this.
First, what is cryptography?
Cryptography is a method used to secure a set of data, to hinder any unwanted party to have access to them. For instance, all our online discussions, web-conferences, random web browsing sessions are safe thanks to cryptographic methods.
The way our data is protected is through a cryptographic algorithm which needs a key to be encrypted and a key to be decrypted. The use of the same private key (a specific string of bits) to encrypt and decrypt is called symmetrical cryptography, whereas the use of one key (“ public”) to encrypt and another one (“ private”) to decrypt is called asymmetrical (or public key) cryptography.
As an example, Alice is willing to talk to Bob but she doesn’t want anyone else to know, so she uses symmetrical cryptography as shown below. Alice’s key is shared with Bob sometime before the actual valuable information is shared. Then Bob can un-encrypt Alice’s message thanks to this key.
This kind of scheme is used in most one-to-one messaging applications like Whatsapp, Messenger or Telegram and in file transfer protocols such as HTTPS and FTPS. It is very commonly used and currently offers good results in terms of security. Two algorithms names that are often mentioned: AES (Advanced Encryption Standard) and One-Time Pad, although this is rarely used because of implementation contraints. AES is currently using most commonly a key size of 128 bits.
However, to avoid the fundamental difficulty of pre-sharing a key, another technology, asymmetrical cryptography, emerged in the 80s. It is in particular necessary when one needs to share information with many users without risking this information to be stolen. Two keys that are generated, one public, and one private. The public one is used by Alice to seal the message and send it to Bob who is uniquely identified by this key in a public register. It serves the purpose of authentication. The paired private one, known only to Bob, is necessary to un-encrypt and read the message.
Two widely used algorithms: RSA and DH, named according to their authors (Rivest, Shamir, & Adleman and Diffie & Hellman). RSA’s key size is rather large, 2048 bits for most applications.
But this is not the whole story. In order to construct a full cryptographic protocol, e.g. TLS for communication security over a computer network, one first needs to choose which security features — primitives — he wants to ensure. TLS is built upon the following primitives : authentication — each participant proves that he is who he pretends to be, key agreement — they share the secret key material that is required to protect their future communications, encryption — they use their shared secret keys to make their communications unintelligible for anyone else , and message integrity — upon receiving a message, they check that it has not been damaged during the transportation. For each of these primitives, the participants can select which specific cryptographic algorithm they wish to employ, e.g. RSA for authentification and key agreement, AES for encryption, HMAC for message integrity.
Quantum Random Number Generators
Public and Private Keys come from a sequence of random numbers generated by a machine, creatively called a Random Number Generator (RNG). Their lengths range from 128 to 3076 bits depending on the algorithms. The longer the keys, the harder they are to recover by a hacker. But the more difficult it is also to share and use them.
However, current RNGs are not able to fully represent randomness which exposes them to the power of powerful computers potentially able to find a pattern in a “reasonable” time frame. This has been proven and the machines needed to find these patterns don’t need to be quantum computers, not even the largest supercomputers in the world such as Summit or Sunway TaihuLight.
The generation of genuine randomness is considered impossible with only classical means but Quantum Physics can be exploited to generate true random numbers. This is at the heart of Quantum Random Number Generators (QRNG).
There are several proven ways to implement these principles, such as the measurement of radioactive decay of a molecule or the use of the quantum states of light. Even if hardware still lacks flexibility and the key generation throughput is limited, progress has been huge over the last year, several startups have emerged to address a large and attractive market. After all, the security of the whole cyber world relies on random number generation.
Quantum Key Distribution
There are two ways for a large computer, whether classical or quantum, to steal secret information. The first way is to recover the key generated during the key agreement phase, the second way is by breaking the encryption algorithm.
Thanks to works that span a couple of decades, the scientific community has designed solutions to generate unbreakable keys: Quantum Key Distribution, a quantum cryptographic primitive that ensures key agreement, including the well known BB84 (by Bennett & Brassard) and E91 (by Ekert) algorithms amongst many others. QKD makes use of, first, a QRNG to generate random keys and, second, a way to safely share them between Alice and Bob.
Suffice it to say here that an extremely profound and elegant principle, the no-cloning theorem, makes sharing cryptographic keys through Quantum Key Distribution extremely safe.
If an eavesdropper tries to copy i.e. “clone” a key that is shared between Alice and Bob, the laws of Quantum physics rule that both Alice and Bob will know it at the end of the protocol, so that they can decide not to use this compromised key. Othewise the eavesdropper would be able to read the message they share.
Is this secret absolutely safe ? Yes … in principle. The devil is in the details and unavoidable compromises to implement such theory make real world QKD non unconditionnaly safe and vulnerable to so called “side-channel attacks”.
Bottom line: thanks to Quantum physics, secret keys are “much safer” with QKD than with classical communications schemes.
This technology is still at its early stage. Indeed, most hardware is expensive, limited to relatively short distances (a few hundred kms), and cumbersome. But start-ups and academics are working tirelessly to improve performances. Most spectacularly, a Chinese team has demonstrated in 2017 that a satellite can successfully perform safe communication through QKD and symmetrical cryptography. They even used the technique to make a secure video call to colleagues in Austria who were 2,500 kilometers away.
Post Quantum Cryptography
While QKD is becoming a key tool for the cryptographic toolbox, it is clear that it won’t be able to satisfy all protection needs. The way it needs to be implemented makes it impractical for many use cases.
The good news is that there are other ways to improve security with so called “quantum-safe” encryption algorithms. These methods don’t need quantum hardware and are actually not based on the laws of quantum physics but on solving mathematical problems that are currently thought to be computationally difficult for both classical and quantum computers.
That means that, while they can be broken by a powerful enough computer, there is no substantial benefit for a hacker to use a quantum computer. PQC can generate both symmetrical and asymmetrical algorithms and there is no need for a hardware based on quantum phenomena such as the ones we’ve mentionned above.
Great, so what’s the catch ? Well, many of the known PQC algorithms are actually not as safe as their inventors claimed them to be. In 2017, NIST (the National Institute of Standards and Technology) initiated a public call for teams worldwide to submit PQC algorithms that would be at the heart of new encryption standards post 2025.
A total of 71 algorithms has been submitted and their robustness against attacks is being tested by teams of researchers all around the world. 6 of them have already been shown unfit for purpose, and 32 are showing weaknesses that might compromise their security.
The updated situation is available in the Post-Quantum Crypto Lounge. Something else to keep in mind is that some algorithms specify computing requirements that will be very hard to implement realistically any time soon. Energy consumption is one of these criteria (see picture above).
Quantum Attacks and how to protect against them
While there are still very active debates about the precise numbers, we estimate that the successful implementation of a Quantum Computer with 100,000 qubits and high gate fidelities will be a strong signal of imminent danger for classical communications. This estimation only holds in the context of our current technological capabilities and will decrease accordingly as future progress in quantum hardware and algorithms design is made, e.g. better gate fidelities and more efficient Quantum Error Correction codes.
As of today, a computer with 100 qubits and good enough gate fidelity is within reach, so we’re some time away from doomsday. Nevertheless, the rapidly increasing chances that a large quantum computer could happen within 10 years is significant enough to put good protections in place now for communications and data which are at the heart of our society. RSA-129 was only a few decades ago …
QRNG, QKD, PQC … these are very active and exciting fields of research and the most mature technologies are coming to the market with a first generation of products being commercialized. Some of them are mentioned in the table above, but if we miss something please let us know ! A key application sector for these technologies is the field of crypto currencies, and other blockchain based applications. Some of these startups are precisely working on that. Hold on for a follow up post on Quantum +Blockchain…
If you have a project in these fields, have started a company or even only are thinking about it, reach out to us. Quantonation is an early stage fund dedicated to Deep Physics, including Quantum Technologies as well as Post Quantum cryptography.
