We initiate the study of communication complexity (CC) for Learning With Errors (LWE) based cryptographic protocols — the mathematical core of the NIST post-quantum standards ML-KEM (FIPS 203) and ML-DSA (FIPS 204). We define the LWE Communication Problem (LWE-CC ): Alice holds secret s ∈ Zn and error vector e; Bob holds matrix A ∈ Zm×n; nqq their joint goal is for Bob to compute b = As + e (mod q) via one-way communication. We make four contributions. First, we prove the lower bound CC(LWE-CCn) ≥ n log2 q bits rigorously. Second, we compute the rank of the communication matrix Mf , fooling set sizes, and discrepancy bounds exactly for small parameters via exhaustive enumeration, producing numbers that do not appear in any prior work: rank(Mf ) ∈ {31, 53, 126} and fooling sets of size ≥ {104, 114, 173} for (n, q) ∈ {(2, 5), (2, 7), (3, 5)}. Third, we observe the empirical pattern rank(Mf ) ≈ qn and state it as Conjecture 1. Fourth, we analyze the hard distribution μ∗ via a coordinate-descent LP, finding it concentrates on zero-secret inputs (s = 0) — a regime that reduces to the INDEX function with no quantum advantage — and conclude the quantum-classical separation must lie in the s ̸= 0 regime where the VSP geometry is active. We also define QV-CCN,k, a new multiparty quantum CC problem derived from the quorum vault recovery protocol of QuantumMail-v2, and prove its classical complexity is Θ(k log p). To our knowledge this is the first CC analysis of any deployed NIST PQC standard operation, and the first formulation of threshold key recovery as a multiparty communication complexity problem.
We initiate the study of communication complexity (CC) for Learning With Errors (LWE) based cryptographic protocols — the mathematical core of the NIST post-quantum standards ML-KEM (FIPS 203) and ML-DSA (FIPS 204). We define the LWE Communication Problem (LWE-CC ): Alice holds secret s ∈ Zn and error vector e; Bob holds matrix A ∈ Zm×n; nqq their joint goal is for Bob to compute b = As + e (mod q) via one-way communication. We make four contributions. First, we prove the lower bound CC(LWE-CCn) ≥ n log2 q bits rigorously. Second, we compute the rank of the communication matrix Mf , fooling set sizes, and discrepancy bounds exactly for small parameters via exhaustive enumeration, producing numbers that do not appear in any prior work: rank(Mf ) ∈ {31, 53, 126} and fooling sets of size ≥ {104, 114, 173} for (n, q) ∈ {(2, 5), (2, 7), (3, 5)}. Third, we observe the empirical pattern rank(Mf ) ≈ qn and state it as Conjecture 1. Fourth, we analyze the hard distribution μ∗ via a coordinate-descent LP, finding it concentrates on zero-secret inputs (s = 0) — a regime that reduces to the INDEX function with no quantum advantage — and conclude the quantum-classical separation must lie in the s ̸= 0 regime where the VSP geometry is active. We also define QV-CCN,k, a new multiparty quantum CC problem derived from the quorum vault recovery protocol of QuantumMail-v2, and prove its classical complexity is Θ(k log p). To our knowledge this is the first CC analysis of any deployed NIST PQC standard operation, and the first formulation of threshold key recovery as a multiparty communication complexity problem.
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.
In post-quantum cryptography (PQC), Learning With Errors (LWE) is one of the dominant underlying mathematical problems. For example, in NIST’s PQC standardization process, the Key Encapsulation Mechanism (KEM) protocol chosen for standardization was Kyber, an LWE-based scheme. Recently the dual attack surpassed the primal attack in terms of concrete complexity for solving the underlying LWE problem for multiple cryptographic schemes, including Kyber. The dual attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to revise the complexity of the dual attack on the LWE-based protocols Kyber, Saber and TFHE. For all these schemes we improve upon the total bit-complexity in both the classical and the quantum setting.As our method of calculating the expected cost of enumeration is fairly general, it might be of independent interest in other areas of cryptography or even in other research areas.
In the last decade, there has been significant progress in the development of quantum computers, with massive investments by major tech companies. It is assumed that once large-scale quantum computers are built, many commonly used public key cryptosystems will no longer be secure. To prevent quantum attacks, researchers are already working on the design of post-quantum cryptographic protocols, and the US National Institute of Standards and Technology (NIST) is holding an international competition to select new cryptographic standards.Lattice-based cryptographic constructions are promising candidates because they offer strong theoretical security guarantees and can be implemented efficiently. One of the most widely used cryptographic primitives based on lattices is the Learning With Errors (LWE) problem introduced by Regev. Later works have proposed structured variants of LWE such as Ring-LWE and Module-LWE, which allow for a more compact representation.In this thesis, we consider two lattice-based NIST candidates for Key Encapsulation Mechanisms (KEMs) and propose new error correction and reconciliation techniques in order to improve their efficiency, their security, as well as their reliability.Unlike some previous works on error correction for lattice-based protocols, we provide rigorous error probability bounds.We first consider FrodoKEM, a lattice-based cryptosystem based on LWE, and introduce a modified error correction mechanism to improve its performance. Our encoder maps the secret key block-wise into a scaled version of the 8-dimensional Gosset lattice E_8. We propose three sets of parameters for our modified implementation. The first implementation outperforms FrodoKEM in terms of plausible security; the second allows to reduce the bandwidth by halving the modulus, and the third allows to increase key sizes.The second KEM we are considering is KyberKEM, which is based on Module-LWE. We propose a reconciliation technique using the lattice E_8, and show that our scheme can outperform KyberKEM in terms of security with comparable error probability and similar bandwidth requirements. We also investigate the use of higher dimensional lattices for reconciliation.
The imminent arrival of large-scale quantum computers necessitates a transition from classical number-theoretic cryptography to post-quantum alternatives. Lattice-based cryptosystems represent the most mature and versatile family among NIST-standardized post-quantum algorithms. This paper presents a rigorous mathematical analysis of security margins for the Learning With Errors LWE and Ring-LWE problems under hybrid attack models that combine lattice reduction BKZ 2.0 with meet-in-the-middle techniques. We derive novel bounds for the root Hermite factor as a function of dimension and block size, proving that current parameter sets recommended by NIST provide a security margin of at least 2128 operations against classical and quantum adversaries. Experimental validation using the fplll library on instances up to dimension n = 1024 confirms our theoretical predictions with a margin of error <0.3%. We further propose a modified error distribution that improves resistance to dual attacks by 17.4% without significant performance degradation.
The imminent threat posed by the advent of quantum computers to contemporary public-key cryptographic schemes, such as RSA and Elliptic Curve Cryptography (ECC), necessitates a fundamental shift in cryptographic paradigms. Shor's algorithm, specifically, presents a catastrophic vulnerability to these foundational security protocols, underpinning global digital communication and commerce. This paper provides a comprehensive exploration into lattice-based cryptography as a robust and promising candidate for a post-quantum cryptographic future. We delve into the mathematical underpinnings of lattices, elucidating the computational hardness of problems like the Shortest Vector Problem (SVP) and the Learning With Errors (LWE) problem, which form the bedrock of their security. The paper reviews the historical development of lattice-based schemes, their theoretical advantages, and their practical implications, particularly in the context of the ongoing NIST Post-Quantum Cryptography standardization process. We analyze the construction of key encapsulation mechanisms (KEMs) and digital signature schemes from lattice problems, comparing their performance characteristics and security guarantees against classical methods. The work argues that lattice-based cryptography offers a compelling alternative to RSA, providing not only quantum resistance but also presenting attractive features in terms of efficiency, design simplicity, and versatility for various cryptographic primitives. The discussion extends to implementation challenges, security analysis, and the broader implications for the global migration towards a quantum-secure cryptographic infrastructure.
A central goal of theoretical computer science is to characterize the limits of efficient computation in a variety of models. We pursue this research objective in the contexts of communication complexity and computational learning theory. In the former case, one seeks to understand which distributed computations require a significant amount of communication among the parties involved. In the latter case, one aims to rigorously explain why computers cannot master some prediction tasks or learn from past experience. While communication and learning may seem to have little in common, they turn out to be closely related, and much insight into both can be gained by studying them jointly. Such is the approach pursued in this thesis. We answer several fundamental questions in communication complexity and learning theory and in so doing discover new relations between the two topics. A consistent theme in our work is the use of analytic methods to solve the problems at hand, such as approximation theory, Fourier analysis, matrix analysis, and duality. (1) We contribute a novel technique, the pattern matrix method , for proving lower bounds on communication. Using our method, we solve an open problem due to Krause and Pudlak (1997) on the comparative power of two well-studied circuit classes: majority circuits and constant-depth AND/OR/NOT circuits. Next, we prove that the pattern matrix method applies not only to classical communication but also to the more powerful quantum model. In particular, we contribute lower bounds for a new class of quantum communication problems, broadly subsuming the celebrated work by Razborov (2002) who used different techniques. In addition, our method has enabled considerable progress by a number of researchers in the area of multiparty communication. (2) Second, we study unbounded-error communication, a natural model with applications to matrix analysis, circuit complexity, and learning. We obtain essentially optimal lower bounds for all symmetric functions, giving the first strong results for unbounded-error communication in years. Next, we resolve a longstanding open problem due to Babai, Frankl, and Simon (1986) on the comparative power of unbounded-error communication and alternation, showing that Scc2n UPPCC: The latter result also yields an unconditional, exponential lower bound for learning DNF formulas by a large class of algorithms, which explains why this central problem in computational learning theory remains open after more than 20 years of research. (3) We establish the computational intractability of learning intersections of halfspaces, a major unresolved challenge in computational learning theory. Specifically, we obtain the first exponential, near-optimal lower bounds for the learning complexity of this problem in Kearns’ statistical query model, Valiant’s PAC model (under standard cryptographic assumptions), and various analytic models. We also prove that the intersection of even two half-spaces on {0, 1}n cannot be sign-represented by a polynomial of degree less than Qpnp , which is an exponential improvement on previous lower bounds and solves an open problem due to Klivans (2002). (4) We fully determine the relations and gaps among three key complexity measures of a communication problem: product discrepancy, sign-rank, and discrepancy. As an application, we solve an open problem due to Kushilevitz and Nisan (1997) on distributional complexity under product versus nonproduct distributions, as well as separate the communication classes PPCC and UPP CC due to Babai, Frankl, and Simon (1986). We give interpretations of ourresults in purely learning-theoretic terms.