The Mechanism, Key Algorithms, and Practical Application Trends of Post-Quantum Cryptography (PQC)

Introduction

Current public-key cryptographic systems, such as RSA and elliptic curve cryptography, face the potential threat of becoming insecure with the advent of large-scale quantum computers. To address this issue, researchers are developing new cryptographic technologies that are resistant to quantum computing attacks. This new field is known as Post-Quantum Cryptography (PQC).

This article will explain the basic mechanisms behind PQC, its key algorithms, standardization trends, and the latest developments and challenges in its practical application.

What is Post-Quantum Cryptography?

PQC refers to a collection of cryptographic algorithms believed to be secure against both quantum and classical computers within realistic time frames. The theoretical vulnerability of RSA and elliptic curve cryptography to quantum computers was first demonstrated in 1994 by Peter Shor, who proposed Shor’s algorithm. This algorithm can efficiently solve problems like integer factorization and discrete logarithms in polynomial time, rendering current public-key cryptographic systems obsolete.

In contrast, PQC relies on mathematical problems that are considered difficult to solve efficiently even by quantum computers. Examples include lattice-based problems, code-based problems, multivariate polynomial problems, and hash-based problems. Since 2016, the National Institute of Standards and Technology (NIST) in the United States has been leading the standardization process for PQC algorithms, which remains ongoing. The NIST PQC Standardization Process serves as one of the most critical reference points for the cryptographic community (refer to the NIST official page for more details).

The need for PQC arises from the transition period required to replace current cryptographic systems before quantum computers become operational. If quantum computers become practical in the 2030s, cryptographic systems must be adapted to PQC beforehand to avoid the risk of retrospective decryption of stored data, known as the “Harvest Now, Decrypt Later” attack.

Key PQC Algorithms

The NIST standardization process has evaluated multiple candidate algorithms. In 2022, the first candidates for standardization were selected, and formal standards (FIPS 203, 204, 205) were announced in August 2024 (NIST, 2024). Below are the key algorithms:

Key Encapsulation Mechanisms (KEM)

CRYSTALS-Kyber (Kyber) was standardized as the KEM for key sharing. Kyber is based on lattice cryptography and derives its security from the computational difficulty of the Module-LWE problem. Compared to RSA and ECDH, Kyber has smaller key sizes and a similar or slightly faster processing speed. According to NIST reports, Kyber-512 provides security equivalent to AES-128 (NIST SP 800-227).

On the other hand, Classic McEliece, based on code theory, has a very large public key (approximately 1MB) but boasts high reliability due to decades of research. Although its standardization is still pending, it is expected to be adopted in limited applications such as embedded systems.

Digital Signatures

For digital signatures, CRYSTALS-Dilithium (Dilithium) and FALCON were standardized. Dilithium is lattice-based and offers a balanced trade-off between key and signature sizes, making it suitable for general-purpose use. FALCON achieves smaller signature sizes but is more complex to implement. SPHINCS+, a hash-based signature algorithm, is also included in NIST standards, though its large signature size limits its practical applications.

Choosing between these algorithms depends on application requirements such as key size, signature size, processing speed, and ease of implementation. For instance, FALCON’s small signature size is advantageous for resource-constrained IoT devices, while Dilithium is recommended for general-purpose servers.

Latest Trends in Practical Application

The adoption of PQC is accelerating as standardization progresses. Below are some key developments:

Integration into Protocol Layers

The integration of PQC into internet protocols is being spearheaded by the IETF. Transport Layer Security (TLS) 1.3 has experimentally implemented a hybrid key-sharing method combining Kyber and X25519 (X25519Kyber768) (IETF draft). Companies like Cloudflare and Google Chrome began trial operations of this hybrid approach in 2023, including performance evaluations in real web traffic (Cloudflare Blog, 2023).

Challenges in Transition

Transitioning to PQC involves several challenges, including:

• Performance Overheads: Many PQC algorithms feature larger key sizes and longer processing times compared to existing algorithms. For example, Classic McEliece has a public key size of approximately 1MB, which can significantly increase network transfer costs.
• Complexity of Hybrid Deployment: During the transition period, hybrid methods combining existing cryptography and PQC are recommended. However, simultaneous key exchanges add complexity to protocol design.
• Compatibility with Existing Systems: Many applications and libraries are not equipped to handle changes in key sizes or support new algorithms. While open-source cryptographic libraries like OpenSSL and BoringSSL are advancing PQC support, adoption in embedded and legacy systems remains slower.
• Stability of Standards: Although NIST standards have been announced, ongoing improvements and alternative proposals continue to emerge. Companies may require additional evaluation periods before committing to adoption.

Corporate and Government Initiatives

The U.S. National Security Agency (NSA) announced a transition plan to PQC for national security systems in 2021. In the EU, the European Telecommunications Standards Institute (ETSI) is advancing PQC standardization. In Japan, the Ministry of Internal Affairs and Communications and the Ministry of Economy, Trade and Industry have developed quantum technology roadmaps and are supporting PQC R&D.

Major cloud service providers such as Google Cloud, Amazon Web Services, and Microsoft Azure began offering PQC-compatible APIs and key management services starting in 2024. For example, Google Cloud KMS experimentally supported Kyber-based key generation in 2024 (Google Cloud Blog).

Editorial Opinion

The transition to PQC presents numerous technical challenges and cannot be accomplished through a simple replacement, according to our editorial team. Evaluating the security requirements and resource constraints of specific applications should be the first step. For instance, long-term data storage may require high-security Kyber-1024, whereas real-time communication might benefit from Dilithium’s quick signature verification. Early reports from the field highlight pitfalls such as increased network and memory usage during the initial implementation of hybrid systems. For IoT devices, the high complexity of implementing FALCON increases the risk of bugs.

Looking ahead, it is predicted that major cryptographic libraries will support PQC by default by 2027, enabling most companies to complete their transition by the late 2020s. However, advancements in quantum computing could accelerate this timeline, emphasizing the importance of starting preparations early.

References

• NIST, “Post-Quantum Cryptography Standardization,” https://csrc.nist.gov/projects/post-quantum-cryptography
• NIST, “FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard,” 2024
• Cloudflare Blog, “Post-Quantum Cryptography in TLS 1.3,” 2023
• Google Cloud Blog, “Google Cloud KMS Now Supports Post-Quantum Cryptography,” 2024
• IETF, “X25519Kyber768 Hybrid Key Exchange,” draft-tls-westerbaan-xyber768d00