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 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.
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.
Recently, American National Institute of Standards and Technology (NIST) announced Kyber as the first KEM candidate to be standardized. The security of Kyber is based on the modular learning with errors (MLWE) problem, which achieves excellent efficiency and size. This work proposes an improved key mismatch on Kyber, which can reduce the number of queries required to recover the secret key. We first transform the problem of finding a certain parameter of ciphertexts into a quantum ordered search problem. Then we give the procedure of finding the value of a parameter in the ciphertexts by the quantum method. Finally, we instantiate this attack method on Kyber512, Kyber768 and Kyber1024. Compared with the existing attack algorithm, our improved attack reduces the number of queries for Kyber512, Kyber768 and Kyber1024 by 63%, 59% and 45%, respectively.
The imminent threat posed by the realization of large-scale, fault-tolerant quantum computers (QCs), capable of leveraging Shor's algorithm to break foundational classical public-key cryptosystems like RSA and ECC, necessitates an immediate and comprehensive shift to Post-Quantum Cryptography (PQC). This urgency is intensified by the "Harvest Now, Decrypt Later" (HNDL) threat, which compromises long-term data confidentiality. The NIST PQC Standardization process has established Lattice-Based Cryptography as the leading family for new standards. This paper presents a comprehensive comparative analysis of major PQC schemes built upon the foundational mathematical problem, Learning with Errors (LWE). We systematically evaluate these LWE-based schemes (CRYSTALS-Kyber, CRYSTALS-Dilithium) by balancing three critical dimensions: cryptographic security (against classical and quantum attacks), efficiency metrics (key size, signature size, and operational speed), and implementation feasibility across diverse hardware environments. Our findings provide essential insights and a structured framework to guide engineers, policy-makers, and organizations in making informed decisions for the strategic and secure migration to quantum-resistant standards in the post-quantum transition era.
Since its proposal by Regev in 2005, the Learning With Errors (LWE) problem was used as the underlying problem for a great variety of schemes. Its applications are many-fold, reaching from basic and highly practical primitives like key exchange, public-key encryption, and signature schemes to very advanced solutions like fully homomorphic encryption, group signatures, and identity based encryption. One of the underlying reasons for this fertility is the flexibility with that LWE can be instantiated. Unfortunately, this comes at a cost: It makes selecting parameters for cryptographic applications complicated. When selecting parameters for a new LWE-based primitive, a researcher has to take the influence of several parameters on the efficiency of the scheme and the runtime of a variety of attacks into consideration. In fact, the missing trust in the concrete hardness of LWE is one of the main problems to overcome to bring LWE-based schemes to practice. This thesis aims at closing the gap between the theoretical knowledge of the hardness of LWE, and the concrete problem of selecting parameters for an LWE-based scheme. To this end, we analyze the existing methods to estimate the hardness of LWE, and introduce new estimation techniques where necessary. Afterwards, we show how to transfer this knowledge into instantiations that are at the same time secure and efficient. We show this process on three examples: - A highly optimized public-key encryption scheme for embedded devices that is based on a variant of Ring-LWE. - A practical signature scheme that served as the foundation of one of the best lattice-based signature schemes based on standard lattices. - An advanced public-key encryption scheme that enjoys the unique property of natural double hardness based on LWE instances similar to those used for fully homomorphic encryption.
In order to resist the security risks caused by quantum computing, post-quantum cryptography (PQC) has been a research focus. Constructing a key encapsulation mechanism (KEM) based on lattices is one of the promising PQC routines. The algebraically structured learning with errors (LWE) problem over power-of-two cyclotomics has been one of the most widely used hardness assumptions for lattice-based cryptographic schemes. However, power-of-two cyclotomic rings may be exploited in the inflexibility of selecting parameters. Recently, trinomial cyclotomic rings of the form Zq[x]/(xn−xn/2+1), where n=2k3l, k≥1,l≥0, have received widespread attention due to their flexible parameter selection. In this paper, we propose Tyber, a variant scheme of the NIST-standardized KEM candidate Kyber over trinomial cyclotomic rings. We provide three parameter sets, aiming at the quantum security of 128, 192, and 256 bits (actually achieving 129, 197, and 276 bits) with matching and negligible error probabilities. When compared to Kyber, our Tyber exhibits stronger quantum security, by 22, 31, and 44 bits, than Kyber for three security levels.
Research on the security of lattice-based public-key encryption schemes against misuse attacks is an important part of the cryptographic assessment of the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) standardization process. In particular, many NIST-PQC cryptosystems follow the same meta-cryptosystem. At EUROCRYPT 2019, Ba˘etu et al. mounted a classical key recovery under plaintext checking attacks (KR-PCA) and a quantum key recovery under chosen ciphertext attacks (KR-CCA). They analyzed the security of the weak version of nine submissions to NIST. In this paper, we focus on learning with error (LWE)-based FrodoPKE, whose IND-CPA security is tightly related to the hardness of plain LWE problems. We first review the meta-cryptosystem and quantum algorithm for solving quantum LWE problems. Then, we consider the case where the noise follows a discrete Gaussian distribution and recompute the success probability for quantum LWE by using Hoeffding bound. Finally, we give a quantum key recovery algorithm based on LWE under CCA attack and analyze the security of Frodo. Compared with the existing work of Ba˘etu et al., our method reduces the number of queries from 22 to 1 with the same success probability.