On August 21, 2023, three U.S. government agencies released a joint factsheet on quantum readiness titled Quantum-Readiness: Migration to Post-Quantum Cryptography. In this note, the Cybersecurity and Infrastructure Security Agency (CISA), the National Security Agency (NSA), and the National Institute of Standards and Technology (NIST) encourage organizations to develop a Quantum-Readiness roadmap for migration to post-quantum cryptographic standards.¹

Quantum preparedness encompasses two aspects. The first aspect involves implementing post-quantum cryptography before quantum computers can successfully compromise classical cryptographic methods. The second aspect involves establishing post-quantum cryptography protocols prior to threat actors harvesting classically encrypted data with the intent to decrypt once quantum computers have acquired this capability.

This latter aspect, dubbed “harvest now, decrypt later”, is often regarded as more critical, especially for entities that store data with a long secrecy lifetime. Insurers and reinsurers who issue policies and agree to contracts covering long-term risks fall into this category.

Quantum Computing

Quantum computing is a paradigm of computing that leverages the principles of quantum mechanics to process and manipulate information. Unlike classical computers, which use bits as the smallest units of data represented as either 0 or 1, quantum computers use quantum bits, or qubits, which can exist in a superposition of states, representing both 0 and 1 simultaneously. This means that a set of two qubits can be in a superposition of four states, which therefore require four numbers to uniquely identify the state. More broadly, the amount of information stored in N qubits equals 2 raised to the power of N (2^N) classical bits.

The principles of quantum mechanics enable quantum computing to perform certain types of calculations much faster than classical computing. Quantum computing achieves polynomial speedup if it solves a problem in time T for which a classical computer requires time T² (for example) or some other polynomial function of T. Similarly, quantum computing achieves exponential speedup if it solves a problem in time T for which a classical computer takes time 2^T (for example) or another exponentially growing function of T.²

Algorithms for quantum computing have been developed for combinatorial and optimization problems and certain types of simulations. Among the well-known quantum algorithms are Shor’s algorithm and Grover’s algorithm.

• Grover’s algorithm provides a quadratic speedup over classical algorithms in searching an unsorted database. It can find the desired item among N items in roughly the square root of N steps, compared to N steps classically. This algorithm has applications in database searching and optimization.
• Shor’s algorithm yields exponential speedup in determining the prime factors of numbers, a process referred to as factorization. This presents a challenge for classical cryptographic systems that rely on the practical difficulty of factoring large numbers to ensure security. This challenge extends to the widely adopted RSA protocol.³

Cryptography

Cryptography bifurcates into symmetric and asymmetric encryption methods. Symmetric encryption, also known as private-key encryption, uses a single key to both encrypt and decrypt data. This means that the same key is used to both scramble and unscramble the data, and the key must be kept secret to prevent unauthorized access. Examples of symmetric encryption algorithms include Advanced Encryption Standard (AES) and 3-DES (Triple Data Encryption Standard).

Asymmetric encryption, also known as public-key encryption, uses a pair of keys - a public key and a private key - to encrypt and decrypt data. The public key is freely available to anyone who needs to send encrypted data, while the private key is kept secret by the owner of the key pair. When someone wants to send encrypted data to the owner of the key pair, they use the owner’s public key to encrypt the data. The owner can then use its private key to decrypt the data. Examples of asymmetric encryption algorithms include RSA and Elliptic Curve Cryptography (ECC).⁴

Symmetric encryption is generally faster and more efficient than asymmetric encryption, but it requires a secure method for distributing the secret key. Asymmetric encryption, on the other hand, does not require a secure key distribution method, but it is generally slower and less efficient than symmetric encryption.

So, while RSA itself isn’t used for the bulk encryption of data due to its relatively slow speed compared to symmetric algorithms, it is heavily used for key exchange, that is securely exchanging the symmetric encryption keys that will be used for the actual data encryption and decryption. This combination of asymmetric and symmetric encryption provides both security and efficiency in secure communication.

The Threat to Classical Cryptography

The threat of quantum computing to classical cryptography is largely confined to asymmetric encryption methods. Although Grover’s algorithm can break symmetric ciphers, it has been argued that increasing the key size can effectively fend off such attacks. Shor’s algorithm (and its variants), on the other hand, can solve all three hard-to-solve mathematical problems that current asymmetric encryption methods rely on for their security, one of which is prime factorization.⁵

RSA is the most prominent instance of an asymmetric encryption method using prime factorization. In simple language, the private key in the RSA encryption protocol is constructed using a pair of randomly selected prime numbers the product of which is a semiprime. The corresponding public key is derived from this semiprime. When transmitting a message, the sender employs the public key, acquired from the intended recipient, to perform the encryption. Upon receiving the encrypted message, the recipient employs the private key, generated from the primes, for decryption.

The RSA encryption key can be broken by factoring the semiprime, here denoted N, that is, by finding the (only) two prime numbers of which N is the product. For illustration, let’s assume N equals 35. Factorizing N is straightforward as it is immediately recognized as the product of 5 and 7, the (only) two prime numbers that generate the semiprime 35.

Modern implementations of RSA ciphers use prime numbers that are hundreds of digits in length. For instance, the RSA number of the 2048-bit RSA protocol that had been generated for the RSA Factoring Challenge launched in 1991 has 617 decimal digits. There is no known algorithm that allows classical computers to determine in a practical amount of time the prime factors of numbers that large.⁶ Nonetheless, Shor's algorithm, introduced in 1994, has demonstrated the capability to solve the factorization problem in polynomial time using quantum computing, thus providing the theoretical basis for breaking RSA.⁷

The implementation of Shor’s algorithm poses a formidable physical challenge. This is because today’s (physical) qubits are subject to errors, which are related to hardware limitations and noise from the surrounding environment.⁸ A 2019 experimental study of Shor’s factoring algorithm on an IBM Q quantum computer reports “excellent” performance in factoring the number 15 (3x5), whereas “deviations from the theoretical results become more noticeable” for 21 (3x7), and the factoring of the number 35 (5x7) failed due to accumulating errors.⁹ Remarkably, the semi-prime 35 is composed of just two decimal digits, a far cry from the 617 decimal-digit RSA number generated for the RSA Factoring Challenge using the 2048-bit protocol.

Although quantum computers have successfully factored larger numbers using alternative algorithms, these methods resemble classical brute-force methods for factor checking. Unlike Shor's algorithm, these approaches are not anticipated to surpass the performance of classical factorization algorithms.¹⁰

The breaking of a sufficiently strong RSA encryption key using Shor’s algorithm may be many years away.¹¹ Large-scale quantum computing requires techniques that keep the errors generated by (physical) qubits from multiplying and spreading. Current error correction methods focus on the encoding of information into multiple physical qubits that are grouped into logical qubits.¹²

Post-Quantum Cryptography (PQC)

In 2016, National Institute of Standards and Technology (NIST) summoned the global community of cryptographers to create and assess encryption methods capable of resisting attacks from an advanced quantum computer, surpassing the power of today's limited machines. By 2022, NIST had selected the first set of encryption tools designed to withstand assaults from future quantum and classical computers alike. These four chosen encryption algorithms are on track to become integral to NIST’s post-quantum cryptographic standard, expected to be finalized by 2024.¹³

Notably, only one candidate has been put forth for key exchange, whereas the other three algorithms are digital signature schemes. The security of the public-key encryption algorithm CRYSTALS-Kyber is based on a hard-to-solve problem known as the shortest vector problem (SVP). Solving a large SVP instance to recover the private key is considered infeasible even for quantum computers.¹⁴

Conclusion

NIST suggests that over the next two decades, there is a plausible chance of quantum computers reaching a scale where they could potentially compromise all currently used public-key encryption methods. The joint factsheet on quantum readiness urges organizations to start preparing early by creating quantum-readiness roadmaps, conducting risk assessments, and engaging vendors. This is essential because data being targeted by threat actors today might still require protection in the future.

This blog was authored by Frank Schmid and reflects his thoughts; however, it was enhanced using Generative AI prior to Gen Re’s editorial and legal review.