In 1994, P. Shor discovered quantum algorithms that can break both the RSA cryptosystem and the ElGamal cryptosystem. In 2007, a Canadian company D-Wave demonstrated the first quantum computer. These events and quick further developments have brought a crisis to secret communication. In 2022, the National Institute of Standards and Technology (NIST) announced 4 candidates-CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, and Sphincs+-for post-quantum cryptography standards. The first 3 are based on lattice theory and the last on Hash functions. In 2024, NIST announced 3 standards: FIPS 203 based on CRYSTALS-Kyber, FIPS 204 based on CRYSTALS-Dilithium, and FIPS 205 based on Sphincs+. The fourth standard based on Falcon is on the way. It is well known that the security of the lattice-based cryptosystems relies on the hardness of the shortest vector problem (SVP), the closest vector problem (CVP), and their generalizations. In fact, the SVP is a ball packing problem and the CVP is a ball covering problem. Furthermore, both SVP and CVP are equivalent to arithmetic problems for positive definite quadratic forms. There are several books and survey papers dealing with the computational complexity of the lattice-based cryptography for classical computers. However, there is no review article to demonstrate the mathematical foundation of the complexity theory. This paper will briefly introduce post-quantum cryptography and demonstrate its mathematical roots in ball packing, ball covering, and positive definite quadratic forms.
In 1994, P. Shor discovered quantum algorithms that can break both the RSA cryptosystem and the ElGamal cryptosystem. In 2007, a Canadian company D-Wave demonstrated the first quantum computer. These events and quick further developments have brought a crisis to secret communication. In 2022, the National Institute of Standards and Technology (NIST) announced 4 candidates-CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, and Sphincs+-for post-quantum cryptography standards. The first 3 are based on lattice theory and the last on Hash functions. In 2024, NIST announced 3 standards: FIPS 203 based on CRYSTALS-Kyber, FIPS 204 based on CRYSTALS-Dilithium, and FIPS 205 based on Sphincs+. The fourth standard based on Falcon is on the way. It is well known that the security of the lattice-based cryptosystems relies on the hardness of the shortest vector problem (SVP), the closest vector problem (CVP), and their generalizations. In fact, the SVP is a ball packing problem and the CVP is a ball covering problem. Furthermore, both SVP and CVP are equivalent to arithmetic problems for positive definite quadratic forms. There are several books and survey papers dealing with the computational complexity of the lattice-based cryptography for classical computers. However, there is no review article to demonstrate the mathematical foundation of the complexity theory. This paper will briefly introduce post-quantum cryptography and demonstrate its mathematical roots in ball packing, ball covering, and positive definite quadratic forms.
In 1994, P. Shor discovered quantum algorithms that can break both the RSA cryptosystem and the ElGamal cryptosystem. In 2007, D-Wave demonstrated the first quantum computer. These events and further developments have brought a crisis to secret communication. In 2016, the National Institute of Standards and Technology (NIST) launched a global project to solicit and select a handful of encryption algorithms with the ability to resist quantum computer attacks. In 2022, it announced four candidates, CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, and Sphincs+, for post-quantum cryptography standards. The first three are based on lattice theory and the last on a hash function. The security of lattice-based cryptosystems relies on the computational complexity of the shortest vector problem (SVP), the closest vector problem (CVP), and their generalizations. As we will explain, the SVP is a ball-packing problem, and the CVP is a ball-covering problem. Furthermore, both the SVP and CVP are equivalent to arithmetic problems for positive definite quadratic forms. This paper will briefly describe the mathematical problems on which lattice-based cryptography is built so that cryptographers can extend their views and learn something useful.
The advent of quantum computing poses a significant existential threat to the security foundations of current public-key cryptography, most notably the widely adopted RSA algorithm. Shor's algorithm, specifically, can efficiently break the mathematical problems underlying RSA and elliptic curve cryptography, necessitating a paradigm shift towards quantum-resistant solutions. This paper explores lattice-based cryptography as the leading candidate for this post-quantum era. We delve into the fundamental mathematical principles of lattices, including hard problems like the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Short Integer Solution (SIS), and Learning With Errors (LWE), which form the bedrock of their security. The paper reviews prominent lattice-based schemes such as NTRU, CRYSTALS-Kyber, CRYSTALS-Dilithium, and Falcon, highlighting their construction, security properties, and performance characteristics. We analyze their resilience against both classical and quantum attacks, discuss their progress in the NIST Post-Quantum Cryptography Standardization process, and evaluate their practical implications and implementation challenges. The discussion emphasizes the provable security, versatility, and efficiency of lattice-based methods, positioning them as the robust and essential successor to RSA for safeguarding digital communications and data in a quantum-enabled future.
The 2024 NIST finalisation of post-quantum cryptography (PQC) standards -- CRYSTALS-Kyber (FIPS 203), CRYSTALS-Dilithium (FIPS 204), FALCON (FIPS 205), and SPHINCS+ -- marks the transition from research to deployment-ready quantum-resistant cryptography. This paper proposes the Post-Quantum Cryptography Algorithm Evaluation (PQCAE) framework, a systematic performance and security analysis of five NIST-standardised and candidate PQC algorithms across five deployment dimensions: key/signature size, computational performance, security level, implementation complexity, and hardware acceleration potential. PQCAE evaluates CRYSTALS-Kyber-768, CRYSTALS-Dilithium-3, FALCON-512, SPHINCS+-128s, and BIKE-L1 on three hardware platforms (x86-64 server, ARM Cortex-M4 embedded, and FPGA). CRYSTALS-Kyber achieves the best overall profile for key encapsulation -- fastest operations (KeyGen 0.06 ms, Encaps 0.08 ms, Decaps 0.09 ms on x86-64) with compact keys. FALCON-512 provides the smallest signature sizes (897 bytes) at moderate computational cost. SPHINCS+ offers the strongest conservative security (hash-based, no lattice assumptions) but largest signatures (8 KB). PQCAE provides migration guidance for organisations transitioning from classical to post-quantum cryptography.
The advent of large-scale quantum computers poses an existential threat to the security of current public-key cryptosystems, such as RSA and Elliptic Curve Cryptography (ECC), which rely on the computational intractability of integer factorization and discrete logarithms. This paper explores lattice-based cryptography as a promising candidate for post-quantum security. We delve into the mathematical foundations of lattices, specifically focusing on hard problems like the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Small Integer Solution (SIS), and Learning With Errors (LWE) problems, which are believed to remain intractable even for quantum computers. We provide a comprehensive review of prominent lattice-based constructions, including NTRU, Kyber, and Dilithium, highlighting their security proofs, efficiency considerations, and suitability for various cryptographic primitives such as public-key encryption, key-exchange mechanisms, and digital signatures. Furthermore, we discuss the challenges and opportunities associated with their deployment, including parameter selection, resistance to side-channel attacks, and integration into existing cryptographic infrastructures. By examining the theoretical underpinnings and practical implications, this work aims to solidify understanding of lattice-based methods as a robust and essential component of the cryptographic landscape in the quantum era, moving beyond the traditional RSA frontier.
Background: The imminent threat posed by cryptographically relevant quantum computers to classical public-key infrastructure specifically RSA and Elliptic-Curve Cryptography (ECC), whose security rests on the conjectured computational intractability of integer factorisation and the discrete logarithm problem respectively has propelled lattice-based cryptography to the centre of global post-quantum standardisation efforts. On 13 August 2024, the United States National Institute of Standards and Technology (NIST) published three landmark Federal Information Processing Standards (FIPS): FIPS 203 (ML-KEM, derived from CRYSTALS-Kyber), FIPS 204 (ML-DSA, derived from CRYSTALS-Dilithium), and FIPS 205 (SLH-DSA, derived from SPHINCS+), with FIPS 206 (FN-DSA, derived from FALCON) in advanced draft. The first three of these standards rest on algebraic structures intimately connected to classical number theory: polynomial rings over integer quotients, cyclotomic fields, and the algebraic geometry of ideal lattices in rings of integers of number fields. Objectives: This article provides: (1) a rigorous mathematical exposition of the lattice problems underpinning NIST’s post-quantum standards, specifically the Learning With Errors (LWE), Ring-LWE (RLWE), Module-LWE (MLWE), Short Integer Solution (SIS), and NTRU problems, and their connections to algebraic number theory; (2) a comparative performance analysis of NIST-standardised lattice-based algorithms against classical RSA and ECC benchmarks; (3) a security analysis examining known classical and quantum attacks on each hard problem; (4) a comparative evaluation of the four NIST-selected algorithms across key size, signature size, and computational benchmarks; and (5) a strategic assessment of the migration challenges facing deployed cryptographic infrastructure. Methods: The study synthesises peer-reviewed literature, NIST official standards documentation (FIPS 203, 204, 205, and draft FIPS 206), and independently published performance benchmarks published between June 2024 and June 2026. Mathematical security analysis is grounded in the worst-case to average-case reductions established by Regev (2005) for LWE and by Lyubashevsky, Peikert, and Regev (2013) [11, 18] for Ring-LWE. Performance data are drawn from Garani (2024) [8], the ARM Cortex-M0+ benchmarking study of Ratnayaka and Fischer (2026) [4], and the cross-platform evaluation by Alzahrani et al. (2025) [2]. Results: NIST’s three August 2024 standards establish a comprehensive lattice-based post-quantum portfolio. ML-KEM-768 produces a 1,184-byte public key and 1,088-byte ciphertext, achieving IND-CCA2 security under the MLWE assumption at NIST Level 3 (AES-192 equivalent). ML-DSA-65 produces 1,952-byte public keys and 3,309-byte signatures under the Module-LWE and Module-SIS assumptions at Level 3. FN-DSA-512 (FALCON, draft FIPS 206) produces 897-byte public keys and 666-byte signatures under the NTRU assumption, offering the most compact lattice-based signatures. Performance benchmarks on an Intel Core i7-12700K (3.6 GHz) confirm that ML-KEM key generation is orders of magnitude faster than RSA-3072 key generation. The algebraic structure of cyclotomic polynomial rings ∑₂ⁿ = Z[x]/(x^n + 1) is central to the efficiency of all three lattice-based NIST standards. Conclusion: Lattice-based cryptography, grounded in the algebraic number theory of ideal lattices over cyclotomic fields, provides the most comprehensive and mathematically well-founded response to the quantum computational threat. The August 2024 NIST standardisation of ML-KEM, ML-DSA, and SLH-DSA represents a landmark in cryptographic history, and the imminent finalisation of FN-DSA will complete the post-quantum toolbox. Organisations should prioritise immediate migration planning, leveraging hybrid classical-quantum schemes during transition, with full transition to NIST post-quantum standards recommended by 2030 per NSA and CISA guidance.
The National Institute of Standards and Technology (NIST) has recently concluded the third round of its Post Quantum Cryptography Standardization Process, selecting four finalist algorithms for standardization: CRYSTALS Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+. These algorithms are designed to withstand attacks from both classical and quantum computers, ensuring the long-term security of digital communications. This paper presents a comprehensive comparative analysis of the security margins and practical deployment readiness of these finalist algorithms. CRYSTALS-Kyber, a key encapsulation mechanism based on the hardness of the Module Learning With Errors problem, offers strong security and efficient performance. CRYSTALS-Dilithium, a digital signature algorithm based on module lattices, provides robust security guarantees and relatively straightforward implementation. FALCON, a lattice-based digital signature algorithm utilizing the Fast Fourier Transform, offers compact signatures and fast verification but faces implementation challenges due to its reliance on floating-point arithmetic. SPHINCS+, a hash-based signature scheme, stands out as a conservative choice with security based solely on the well-established security of hash functions. The analysis reveals that while each algorithm has its strengths, they also face unique challenges in terms of side-channel vulnerabilities, formal security proofs, and performance trade-offs. The practical deployment of these algorithms requires careful consideration of specific security requirements, performance needs, and resource constraints. Ongoing research efforts aim to enhance the algorithms' resistance against advanced attacks, optimize their performance across diverse platforms, and develop standardized and secure hybrid cryptographic systems. The transition to post-quantum cryptography will involve challenges such as interoperability with legacy systems, the need for clear standards and regulatory guidance, and the costs associated with software and hardware updates. Continued engagement with the cryptographic community and monitoring of the evolving security landscape will be crucial for ensuring a secure and effective migration to post-quantum cryptography.