The Post-Quantum Cryptography

Introduction

Safe digital communication for organizations and individuals is protected online by using cryptography, whether making an online purchase from a favorite online store or sending an email to a friend or colleague. Imagine the impact if cybercriminals could break the cryptographic algorithms used to encrypt all our banking, medical information and history, or any sensitive data we use in our day-to-day digital life. As we venture into a time where quantum computing powers could break all conventional encryption methods, the emergence of post-quantum cryptography takes center stage and should be on top of our priorities, providing us with alternatives to keep our digital interactions and data secured. Developing any new quantum-resistant cryptosystems must be done openly and in complete transparency and subjected to rigorous testing and analysis.

A classical computer BIT is a ZERO (0) or a ONE (1), arranged in logical order that makes sense when mapped to a natural language [1]. Quantum computing uses the quantum bit (qubit) as the basic unit of information rather than the conventional bit. Processing information is conducted fundamentally in different ways to the conventional classical computers, which can only be represented by either “1” or “0” of binary information at any single time. Quantum computing uses qubits, which can represent both 0 and 1 simultaneously. This main characteristic of an alternative system of qubits is what permits the coherent superposition of ones and zeros, the digits of the binary system around which all computing revolves [2].

The Quantum Threat

The previously deemed implausible attacks capable of undermining our current cryptographic algorithms have become feasible due to the emergence of powerful quantum computing, which exploits the principles of quantum mechanics. It is evident that numerous malicious actors and cybercriminals are actively harvesting encrypted data, anticipating that forthcoming technologies will soon break these algorithms—i.e., hack now, crack later [1].

These attacks can result in harvesting and breaking any session key, stealing encrypted and well-protected data from cloud storage. Data encryption is what protects us today in many major breaches, as it renders the data useless in the wrong hands. Conventional cryptographic algorithms like Rivest-Shamir-Adleman (RSA) rely on mathematical large prime equations that are extremely difficult to solve using classical computers. Quantum computing will exploit these inherent patterns and solve those problems exponentially much faster, rendering many existing encryption methods vulnerable to quantum-powered attacks. By making fraudulent digital certificates and deriving private keys from public keys, intercepting any website-encrypted communication becomes an easier task for cybercriminals.

For example, to protect a website and obtain the Hypertext Transfer Protocol Secure (HTTPS) padlock symbol, we use a protocol called Transport Layer Security (TLS) v1.3. The TLS uses a 256-bit key for data encryption and decryption, turning plaintext into ciphertext (Figure 1). In the current computing powers, a supercomputer will take a million years to crack this encryption. Using quantum computing powers to crack the same key will take ~8 hours.

The Quantum Cryptographic Compromise

In today’s encryption, we use symmetric and asymmetric cryptography. Symmetric uses the same key to encrypt and decrypt the data. The most current secure algorithm used is the Advanced Encryption Standard (AES), which can be implemented using 128 bits and 256 bits. The main difference between 128- and 256-bit blocks is that 128 uses 10 rounds of processing to generate keys, while 256 uses 14 rounds of processing to generate keys.

Asymmetric cryptography uses two keys—public and private cryptographic keys in combination. As the name indicates, the public key is given to anyone we want to share the encrypted data with, and the private key is kept well protected in our possession. Mathematically speaking, these keys are very large prime numbers. Examples on asymmetric algorithms are Rivest, Shamir, Adleman (RSA), Diffie-Hellman (DH), and Elliptic Curve Cryptography (ECC).

Breaking Bad in The Era of Quantum

Two important algorithms worth discussing are Shor and Grover. Combining these algorithms with the might of quantum computing powers will easily break most of our current cryptographic algorithms and encryption used today. They were considered and used in analyzing post-quantum cryptography (PQC). Part of the National Institute of Standards and Technology’s (NIST’s) efforts in initiating a process to solicit, evaluate, and standardize one or more quantum-resistant, public-key cryptographic algorithms, PQC aims to provide a robust security in a quantum-computing landscape, ensuring that encrypted data remains confidential and its integrity is well preserved [3–5].

Several misconceptions surround PQC. One is the notion that achieving quantum-resilient cryptography necessitates the use of quantum computers. Another misconception is the belief that no immediate measures can be taken to safeguard data against quantum-enabled decryption. Similarly, some individuals mistakenly assume that it is solely the responsibility of the Cloud provider to secure their Cloud-based data from quantum threats [1].

Quantum computing, particularly with the Shor algorithm, offers a vastly accelerated approach to solving factoring problems. This includes tackling challenges like integer factorization and elliptic curve and discrete logarithm problem. Consequently, encryption methods such as RSA, DH, and ECC can potentially be compromised within a matter of minutes or hours, as opposed to the previously projected timeframe of thousands of years.

While the Shor algorithm takes care of asymmetric cryptography using factoring, the Grover algorithm will take care of symmetric cryptography by searching for unstructured databases solving function inversion, cutting the brute forcing time of any symmetric algorithm in half. Also known as the Quantum Search algorithm, the Grover algorithm provides a quadratic speedup for unstructured searches using O(√ n) evaluations, speeding searches from (n/2) to (√ n) steps [6].

Is My Organization at Risk?

The data that requires protection for a prolonged period is the data we must protect (Figure 2). The threat is now, and the critical impact is soon. Preparing for post-quantum cryptography should be prioritized based on the data’s shelf life and system’s lifetime durations.

According to a McKinsey study [7], while quantum computers may not be able to crack conventional encryption protocols until 2030, many cybersecurity and risk managers should evaluate their options today.

Using a cryptographically relevant quantum computer will make it very easy to break the traditional algorithmic encryptions currently used. The decision-makers within the cybersecurity industry must start thinking of these problems and act. What was expected to happen in 20 years has started evolving much faster than expected and is taking shape.

Entering the Post-Quantum Cryptography Era

Many industries and sectors follow rigorous standards, regulations, and industry compliance, one of which is the cryptographic standard dictating what should be used to encrypt sensitive data. An example is using the Federal Information Processing Standard (FIPS) 140-2 with the AES 256-bit keys or the more efficient NIST-approved FIPS 197 or FIPS 180-4, as defined in Special Publication 800-38D for encrypting data at rest [4].

NIST already announced their six years’ competition selection for Quantum-Resistant Cryptographic algorithms [5]:

“Today’s announcement is an important milestone in securing our sensitive data against the possibility of future cyberattacks from quantum computers,” said Secretary of Commerce Gina M. Raimondo. “Thanks to NIST’s expertise and commitment to cutting-edge technology, we are able to take the necessary steps to secure electronic information so U.S. businesses can continue innovating while maintaining the trust and confidence of their customers.”

For general encryption and securing website access, NIST selected the Cryptographic Suite for Algebraic Lattices (CRYSTALS)-Kyber algorithm [8]. Kyber is an IND-CCA2-secure key encapsulation mechanism (KEM) whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. Kyber-512 aims at security equivalent to AES-128, Kyber-768 aims at security equivalent to AES-192, and Kyber-1024 aims at security equivalent to AES-256.

For users interested in using the Kyber algorithm, a hybrid mode combined with an established “pre-quantum” security like the elliptic-curve Diffie-Hellman is recommended. Using the Kyber-768 parameter set will provide decent protection, as it achieves more than 128 bits of security against all known classical and quantum attacks.

Table 1 gives an indication of the performance of Kyber, where the benchmarks were obtained using the Intel Core i7 Haswell central processing unit (CPU). The table displays the key generation cycles (gen), the encapsulation cycles (enc), and the decapsulation cycles (dec). For higher security encryption, NIST selected CRYSTALS-Dilithium, FALCON, and SPHINCS+, recommending CRYSTALS-Dilithium as the primary.

Table 1. Kyber Algorithm Performance [8]

Kyber-512
Sizes (in bytes)		Haswell Cycles (ref)		Haswell Cycles (avx2)
sk:	1632	gen:	122684	gen:	33856
pk:	800	enc:	154524	enc:	45200
ct:	768	dec:	187960	dec:	34572
Kyber-768
Sizes (in bytes)		Haswell Cycles (ref)		Haswell Cycles (avx2)
sk:	2400	gen:	199408	gen:	52732
pk:	1184	enc:	235260	enc:	67624
ct:	1088	dec:	274900	dec:	53156
Kyber-1024
Sizes (in bytes)		Haswell Cycles (ref)		Haswell Cycles (avx2)
sk:	3168	gen:	307148	gen:	73544
pk:	1568	enc:	346648	enc:	97324
ct:	1568	dec:	396584	dec:	79128

The Dilithium algorithm is a digital signature scheme that is strongly secure under chosen message attacks based on the hardness of lattice problems over module lattices. The security notion means that adversaries having access to a signing oracle cannot produce a signature of a message whose signature they have not yet seen nor can they produce a different signature of a message that they have already seen signed [9].

For users interested in using the Dilithium algorithm, a hybrid mode combined with an established “pre-quantum” signature scheme is recommended. Using the Dilithium3 parameter set will achieve more than 128 bits of security against all known classical and quantum attacks.

Table 2 gives an indication of the performance of Dilithium, where the benchmarks were obtained using the Intel Core i7 Skylake CPU. The table displays the key generation cycles (gen), the encapsulation cycles (enc), and the decapsulation cycles (dec).

Table 2. Dilithium Algorithm Performance [9]

Dilithium2
Sizes (in bytes)		Skylake Cycles (ref)		Skylake Cycles (avx2)
		gen:	300751	gen:	124031
pk:	1312	sign:	1355434	sign:	333013
sig:	2420	verify:	327362	verify:	118412
Dilithium3
Sizes (in bytes)		Skylake Cycles (ref)		Skylake Cycles (avx2)
		gen:	544232	gen:	256403
pk:	1952	sign:	2348703	sign:	529106
sig:	3293	verify:	522267	verify:	179424
Dilithium5
Sizes (in bytes)		Skylake Cycles (ref)		Skylake Cycles (avx2)
		gen:	819475	gen:	298050
pk:	2592	sign:	2856803	sign:	642192
sig:	4595	verify:	871609	verify:	279936

While we have discussed two of the cryptographic quantum-resistant algorithms announced by NIST, the following other postquantum cryptography protocol proposals are worth mentioning [10, 11].

• FrodoKEM – A post-quantum cryptography project that is a collaboration between researchers and engineers at Centrum Wiskunde & Informatica (CWI), Google, McMaster University, Microsoft Research, NXP Semiconductors, Stanford University, and the University of Michigan. The International Organization for Standardization has approved FrodoKEM and two other algorithms.
• SIKE and SIDH (Supersingular Isogeny Key Encapsulation) and (Supersingular Isogeny Diffie-Hellman) – Use arithmetic operations of elliptic curves over finite fields to build a key exchange; they are insecure and should not be used.
• Picnic – A public-key digital signature algorithm. Unlike most other public-key cryptographies, Picnic is not based on hard problems from a number theory. Instead, it uses a zero-knowledge proof and symmetric key primitives.
• qTESLA – a post-quantum signature scheme based upon the ring-LWE problem.

Conclusions

Although post-quantum cryptography holds significant promise, its adoption does not come without major challenges. One main obstacle is transitioning from the conventional established cryptographic methods and algorithms to a new era of algorithms. Organizations must thoroughly and cautiously manage this transition to ensure a flawless shift while maintaining the integrity, availability, and confidentiality of their data.

Failing to plan is planning to fail. From this, the following considerations toward post-quantum cryptography are recommended:

• Create an inventory in which all applications and infrastructure within the environment using public key cryptography are identified.
• Conclude crown jewels data currently protected by public key cryptography.
• Design a clear transition plan for using PQC algorithms within the environment, including testing and adopting new PQC algorithms and retiring the old ones.
• Work closely with all vendors and third parties involved regarding the PQC requirements and maintain clear engagement with all stakeholders regarding the implementation of new algorithms.

One of the projects that users and their organizations should monitor is the Open Quantum Safe project, which is an open-source project that aims to support the development and prototyping of quantum-resistant cryptography. Their liboqs library is a collection designed to further post-quantum cryptography and implementations of quantum-safe KEM and Digital Signature algorithms. They have produced very interesting cryptographic integrations, such as the Post-Quantum Crypto VPN, which is a fork of OpenVPN integrated with post-quantum cryptography; the Post-Quantum Secure Shell (SSH), which is a fork of OpenSSH 7.7; and the Post-Quantum TLS, which is a fork of OpenSSL [12].

References

1. Garris, G. “Quantum Security – Quantum Computing and the Threat to Cybersecurity.” Cybersecurity and Information Systems Information Analysis Center webinar, https://csiac.org/webinars/quantum-security-quantum-computing-the-threat-to-cybersecurity/, accessed on 24 August 2023.
2. Sutor, R. S. Dancing With Qubits: How Quantum Computing Works and How It Can Change the World. Packt Publishing, 28 November 2019.
3. NIST. “Post-Quantum Cryptography – Security (Evaluation Criteria).” https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/evaluation-criteria/security-(evaluation-criteria), accessed on 24 August 2023.
4. NIST. “NIST Selects ‘Lightweight Cryptography’ Algorithms to Protect Small Devices.” https://www.nist.gov/news-events/news/2023/02/nist-selects-lightweight-cryptography-algorithms-protect-smalldevices#:~:text=Currently%2C%20the% 20most%20efficient %20NIST,in%20effect%20for%20general%20use, accessed on 24 August 2023.
5. NIST. “NIST Announces First Four Quantum-Resistant Cryptographic Algorithms.” https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms, accessed on 24 August 2023.
6. Quantum Algorithm Zoo. “Algorithm: Quantum Cryptanalysis/Searching/Hidden Shift.” https://quantumalgorithmzoo.org/, accessed on 24 August 2023.
7. McKinsey Digital. “When—and How—to Prepare for Post-Quantum Cryptography.” https://www.mckinsey.com/capabilities/mckinsey-digital/our-insights/when-and-how-to-prepare-for-post-quantum-cryptography#/, accessed on 24 August 2023.
8. Crystals.org. “CRYSTALS – Cryptographic Suite for Algebraic Lattices.” Kyber Home, https://pq-crystals.org/kyber/index.shtml, accessed on 24 August 2023.
9. Crystals.org. “CRYSTALS – Cryptographic Suite for Algebraic Lattices.” Dilithium Home, https://pq-crystals.org/dilithium/index.shtml, accessed on 24 August 2023.
10. Microsoft. “Post-quantum Cryptography.” https://www.microsoft.com/en-us/research/project/post-quantum-cryptography/, accessed on 24 August 2023.
11. Microsoft. “Supersingular Isogeny Key Encapsulation (SIKE).” https://www.microsoft.com/en-us/research/project/sike/, accessed on 24 August 2023.
12. Open Quantum Safe. “Open Quantum Safe Software for Prototyping Quantum-Resistant Cryptography.” https://openquantumsafe.org/, accessed on 24 August 2023.

Biography

Chadi Saliby is a subject matter expert at CompTIA and Adjunct Professor at Deakin University Centre for Cyber Security Research and Innovation. Prior to his current role, he worked in one of the big four banks in Australia’s financial sector as a cybersecurity expert and on the front line of one of the biggest and more successful cybersecurity organizations in their five-star incident response and security operations center team. He acquired various cybersecurity industry certificates from (ISC)2, Microsoft, Cisco, HP, and CompTIA. Mr. Saliby graduated from the Centre International Des Sciences Technique in business computer and programming and continued his MBA Magister en Business et Administration at Sorbonne.