If you’re reading this article from an internet browser, take a close look at the little lock at the top of the address bar. Click on it. Now click on “Certificates”. Finally, select the ‘Certificate details’ tab. Notice the value “Public Key”, what do you see? RSA, maybe DSA or even ECDSA. Well, in a few years, you’ll stop seeing those algorithms. Why? Because the quantum computers will have wiped them off the map.
Look now at other secure communication protocols: TLS, responsible for the little lock that protects web pages and practically protects everything; the end-to-end encryption of WhatsApp or Zoom, etc. Think about digital signatures: contract validation, identification of software authorship, identity verification, guarantee of ownership in blockchain, etc. Those same algorithms (RSA, DSA, ECDSA) are everywhere, but their days are numbered: 10 or 15 years, at most. Will it be the end of privacy? No more secrets? Luckily, no. There is cryptographic life beyond RSA and DSA and ECDSA.
Welcome to the post-quantum future!
Hello, Quantum Computers. Goodbye, Classic Cryptography
Quantum computing is more efficient than classical computing in some tasks, such as solving the mathematical problems on which rest the security of the public key algorithms that we use today for encryption and digital signature: RSA, DSA, ECDSA, ECC, DH, etc.
In a world of quantum computers, cryptography requires algorithms based on mathematical problems that are impervious to advances in quantum computing. Fortunately, such cryptographic algorithms have existed for decades. They are collectively known as post-quantum cryptography (PQC). The three best studied alternatives to date are:
- Hash-based cryptography: as the name suggests, they use secure hash functions, which resist quantum algorithms. Their disadvantage is that they generate relatively long signatures, which limits their use scenarios. Leighton-Micali Signature Scheme (LMSS) or Merkle signature schemes are among the strongest candidates to replace RSA and ECDSA.
- Code-based cryptography: Code theory is a mathematical specialty that deals with the laws of information coding. Some coding systems are very difficult to decode, even requiring exponential time for a quantum computer. The best studied cryptosystem to date is that of McEliece, another promising candidate for key exchange. Its drawback: keys millions of bits long.
- Lattice-based cryptography: possibly the most active field of research in post-quantum cryptography. A lattice is a discrete set of points in space with the property that the sum of two points of the lattice is also in the lattice. A difficult problem is to find the shortest vector in a given lattice.
For their resolution, all classical algorithms require time that grows exponentially with the size of the lattice and it is believed that the same will happen with quantum algorithms. Currently there are numerous cryptosystems based on the Shortest Vector Problem. The example that has perhaps attracted the most interest is the NTRU public key encryption system.
So, if we already have substitutes for RSA, DSA, ECDSA, why not continue with the old algorithms until the first quantum computers capable of breaking them appear, and then switch with a click to the post-quantum ones?
In Cryptography, Births Are Long and Painful
There are four powerful reasons to start working now on the transition to post-quantum cryptography:
- We need time to improve the efficiency of post-quantum cryptography: to give you an idea, to achieve the security provided by b-bit keys in ECC, post-quantum algorithms may require keys between b2 and b3 bits, so do the math. Efficiency improvement is especially critical when thinking about constrained devices, widely used in IoT applications, and main targets of the PQC.
- We need time to build confidence in post-quantum cryptography: NIST has initiated a process to request, evaluate, and standardize one or more PQC algorithms for digital signature, public key encryption, and session keying. The IRTF Crypto Forum Research Group has completed standardisation of two hash-based signature algorithms, XMSS and LMS, which are also expected to be standardised by NIST.
- We need time to improve the usability of post-quantum cryptography: these standards should be incorporated into the cryptographic libraries used by the most popular programming languages and by the cryptographic chips and hardware modules.
The Open Quantum Safe (OQS) project is working on liboqs, an open source C library for PQC algorithms. These will then have to be integrated into cryptographic standards and protocols, such as TLS, X.509, IKEv2, JOSE, etc. OQS is also working on liboqs integrations into OpenSSL and OpenSSH. Then, these standards and protocols should be included by all vendors in their products: from hardware manufacturers, to software manufacturers.
- We need to protect some secrets for a long time: there is very valuable data that has a long life span: employee records, health records, financial records, etc. In the military and industrial field the need to secure secrets for a long time is even greater. For example, design plans for new military weapons or commercial aircraft could be stolen today, encrypted with classic algorithms, waiting for quantum computers to decipher them even decades after the theft.
In short, we are not yet ready for the world to switch to post-quantum cryptography at the touch of a button.
Will Quantum Cryptography Be The Best Weapon Against Quantum Computers?
Quantum cryptography today boils down to quantum key distribution (QKD): exchanging a random key between two unauthenticated ends with the certainty that any interception attempt will be detected. This key can then be used to encrypt confidential information using Vernam’s algorithm to ensure perfect secrecy, even in the face of an attack from a quantum computer.
Not so fast! Unfortunately, QKD has many practical drawbacks that make its adoption inadvisable, at least in the near future:
- Since QKD protocols do not provide authentication, they are vulnerable to man-in-the-middle attacks in which an adversary can agree to individual secret keys shared with two parties who believe they are communicating with each other.
- QKD requires specialised and extremely expensive hardware.
- The distances at which QKD can transmit keys are currently modest, in the range of a few thousand kilometres with very delicate experimental prototypes, far from commercially viable.
- QKD is used to agree on keys, but not to digitally sign information. Cryptography goes far beyond symmetrical encryption.
In short, for most real-world communications systems out there, PQC will provide an antidote to quantum computing that is more effective and efficient than QKD.
Where Will We See Applications of PQC In The Near Future?
According to the report Post-Quantum Cryptography (PQC): A Revenue Assessment released on the 25th June by the quantum technology analyst firm Inside Quantum Technology, the market for post-quantum cryptography software and chips will soar to $9.5 billion by 2029. While PQC’s capabilities will be incorporated into numerous devices and environments, according to the report, PQC’s revenues will be concentrated in web browsers, IoT, 5G, law enforcement (police, military, intelligence), financial services, health services and the cybersecurity industry itself.
If everyone is aware of the shadow of quantum computing over classical cryptography, why aren’t they investing more resources in PQC right now? Because all the players are waiting for the NIST (National Institute of Standards and Technology) to complete Round 3 of its PQC standards, which will happen in 2023.
From that date, services offered by the cybersecurity industry will include NIST-standardised PQC algorithms. For example, Inside Quantum Technology believes that manufacturers will provide PQC offerings as a service for email and VPN. In addition, the cybersecurity industry will recommend, develop, and implement PQC software for their customers. They predict that by 2029 the revenue from PQC-related cybersecurity offerings will likely reach $1.6 billion.
Make The Leap to PQC Before It’s Too Late
If your organization is currently handling encrypted information whose confidentiality needs to be guaranteed for more than 10 years, you’d better take a look at the PQC product offering.
In the meantime, you may want to take a look at the commercial solutions available to your organization to see if they can be put into production. Since you will have to make the leap to PQC sooner or later, it’s best to calmly examine strategies for reducing the costs of technology changeover and preparing for the transition.
Because you can be sure of one thing: the day of the PQC will come.