We put forward a new approach for achieving non-interactive zero-knowledge proofs (NIKZs) from the learning with errors (LWE) assumption (with subexponential modulus to noise ratio). We provide a LWE-based construction of a hidden bits generator that gives rise to a NIZK via the celebrated hidden bits paradigm. A notable feature of our construction is its simplicity. Our construction employs lattice trapdoors, but beyond that uses only simple operations. Unlike prior solutions, we do not rely on a correlation intractability argument nor do we utilize fully homomorphic encryption techniques. Our solution provides a new methodology that adds to the diversity of techniques for solving this fundamental problem.
We put forward a new approach for achieving non-interactive zero-knowledge proofs (NIKZs) from the learning with errors (LWE) assumption (with subexponential modulus to noise ratio). We provide a LWE-based construction of a hidden bits generator that gives rise to a NIZK via the celebrated hidden bits paradigm. A notable feature of our construction is its simplicity. Our construction employs lattice trapdoors, but beyond that uses only simple operations. Unlike prior solutions, we do not rely on a correlation intractability argument nor do we utilize fully homomorphic encryption techniques. Our solution provides a new methodology that adds to the diversity of techniques for solving this fundamental problem.
We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.
The Learning with Errors (LWE) problem asks to distinguish noisy samples s^T A + e^T mod q from uniformly random values given the random matrix A. In this work, we show that a variant called Leaky LWE, where the distinguisher receives additionally noisy leakages (s^T, e^T) L + f^T of the LWE secret s and error e for low-norm matrix L chosen adaptively by the distinguisher after seeing A, is not easier than the standard LWE of the same dimensions up to polynomial losses in the noise level and the modulus. More generally, we show that the Leaky LWE problem is hard even if the public matrix A is structured and/or hinted and if the non-leaky parts of the secret and error do not follow Gaussian distributions, as long as the corresponding LWE problem without leakage is hard. Our reduction from LWE to Leaky LWE unifies and extends prior results on the Error-Leakage LWE problem [Döttling-Kolonelos-Lai-Lin-Malavolta-Rahimi, EUROCRYPT'23], where L only acts on the error e and the Hint-MLWE problem [Kim-Lee-Seo-Song, CRYPTO'23], where L is restricted to concatenations of random Gaussian scalar matrices not controlled by the distinguisher. Previously, the Hint-MLWE and Error-Leakage LWE assumptions were used as computational replacements of the statistical noise flooding technique in security proofs which led to improved parameters in lattice-based cryptographic constructions such as zero-knowledge proofs, threshold signatures and registration-based encryption. We provide lemmas which abstract out such computational arguments based on Leaky LWE.
We study non-interactive zero-knowledge proofs (NIZKs) for NP satisfying: 1) statistical soundness, 2) computational zero-knowledge (ZK) and 3) certified-everlasting zero-knowledge (CE-ZK). The CE-ZK property allows a verifier of a quantum proof to revoke the proof in a way that can be checked (certified) by the prover. Conditioned on successful certification, the verifier's state can be efficiently simulated with only the statement, in a statistically indistinguishable way. Our contributions regarding these certified-everlasting NIZKs (CE-NIZKs) are as follows:
- We identify a barrier to obtaining CE-NIZKs in the CRS model via generalizations of known interactive ZK proofs that satisfy CE-ZK.
- We circumvent this by constructing CE-NIZK using non-black-box use of NIZK for NP satisfying certain properties, along with OWFs. As a result, we obtain CE-NIZKs for NP in the CRS model, based on polynomial hardness of the learning with errors (LWE) assumption.
- In addition, we observe that the aforementioned barrier does not apply to the shared EPR model. We leverage this to construct CE-NIZK for NP in this model based on any statistical binding hidden bits generator, which is known from LWE. The only quantum computation here involves single-qubit measurements of the EPR pairs.
We introduce Learning with Correlated Errors (LCE), a new lattice-based computationalhardness assumption in which observed samples carry noise generated by a low-rank linearcorrelation structure. Formally, given samples (A, b = As + Ce0 + e1 mod q), whereC ∈ Zm×rq is a publicly known correlation matrix and e0, e1 are short Gaussian vectors, thetask is to recover the secret s.Unlike LWE, the noise in LCE is globally correlated: up to r independent root noise sourcesdrive m observations simultaneously. Unlike the recent hybrid sparse-small assumptions ofGhosal et al. [GJL+25], LCE preserves a lattice structure that enables a reduction from theLearning with Errors (LWE) problem, thereby inheriting its worst-case hardness guarantees.We prove: (1) Worst-case hardness via reduction: We give a polynomial-timereduction from Decision-LWE to Decision-LCE, establishing that LCE is at least as hardas LWE and thereby inheriting its worst-case lattice hardness guarantees. (2) Search-to-Decision reduction: Search-LCE and Decision-LCE are polynomial-time equivalent (viaan explicit n-hybrid argument). (3) Cryptographic construction: an IND-CPA-securepublic-key encryption scheme from Decision-LCE. (4) Quantum resistance: by composingour reduction with Regev’s quantum reduction, we show that LCE resists known quantumattacks, with quantum lattice sieving requiring an estimated 20.265n quantum gates (matchingthe estimated cost for standard LWE).LCE provides a new, independently motivated hardness foundation for post-quantumcryptography and adds meaningful assumption diversity beyond LWE and LPN.
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.
Abstract. We design an efficient commitment scheme, and companion zero-knowledge proofs of knowledge, based on the learning with errors over rings (RLWE) problem. In particular, for rings in which almost all elements have inverses, we construct a perfectly binding commitment scheme whose hiding property relies on the RLWE assumption. Our scheme maps elements from the ring (or equivalently, n elements from Fq) to a small constant number of ring elements. We then construct Σ-protocols for proving, in a zero-knowledge manner, knowledge of the message contained in a commitment. We are able to further extend our basic protocol to allow us to prove additive and multiplicative relations among committed values. Our protocols have a communication complexity of O(Mn log q) and achieve a negligible knowledge error in one run. Here M is the constant from a rejection sampling technique that we employ, and can be set close to 1 by adjusting other parameters. Previously known Σ-protocols for LWE-related languages either relied on “smudging ” out the error (which necessitates working over large fields, resulting in poor efficiency) or only achieved a noticeable or even constant knowledge error (thus requiring many repetitions of the protocol).