Questions tagged [lwe]

Learning with Errors is a form of lattice problem used in the design of cryptographic primitives. LWE is based on the Closest Vector Problem (CVP).

Filter by
Sorted by
Tagged with
10
votes
2answers
1k views

Why is Ring-LWE more efficient compared to LWE?

Can someone please tell me why is the Ring-LWE more efficient? By introducing polynomials in place of matrices, what kind of optimizations do we introduce that make Ring-LWE more efficient?
8
votes
1answer
183 views

Number of LWE samples in NewHope

This is regarding the number post-quantum key exchange protocol New-Hope (https://eprint.iacr.org/2015/1092.pdf). In the paper, we can see that the number of samples generated by the protocol is $2n$ ...
8
votes
1answer
225 views

LWE: error and float operations

Background I'm trying to make sense of the error in implementations of LWE and R-LWE. In LWE and R-LWE error is added to vectors in lattices to make it computationally infeasible to recover any ...
7
votes
2answers
364 views

Understand LWE(Learning With Error) negligible error probability

According to Regev's paper, p15 Correctness. Note that if not for the error in the LWE samples, $b-⟨a, s⟩$ would be either 0 or ⌊ q ⌋ depending on the encrypted bit, and decryption would always be ...
7
votes
1answer
387 views

NewHope and NIST's Post-quantum standardization

Where can I find NIST's reasoning to eliminate NewHope from the 3rd round of the post-quantum competition? I see all the lattice KEMs finalists are based on modules. Is being a ring-based KEM ...
7
votes
1answer
486 views

Are LPN and LWE problems equivalent?

Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits. But, this also makes LPN seem very related to the problem ...
7
votes
1answer
114 views

Is LPN not as important as LWE and SVP?

I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, ...
7
votes
1answer
408 views

A RLWE promise problem

Let $(R , \chi$) be a standard RLWE problem instance. I.e. $R$ is a finite degree polynomial ring over a finite field and $\chi$ is some gaussian distribution over R with small variance. I wonder ...
7
votes
0answers
194 views

Does there exist trapdoor permutation from lattices?

It seems that the lattice functions are either surjective (SIS) or injective (LWE), due to the error that is basically intended to destroy the structure and provide security. I was wondering whether ...
6
votes
1answer
156 views

Decision to Search LWE when modulus $q=p^e$

I am reading Applebaum et al.. In Lemma 1. (page 7), Applebaum et al. proved the decision to search reduction when the modulus $q=p^e$ for prime $p$. In the proof, they define the hybrid ...
5
votes
3answers
287 views

A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem

In this paper (A simple provably secure key exchange by Ding et al.) At page number 8, the author gives correctness of the technique as follows then SK A = SKB with overwhelming probability i.e. if ...
5
votes
2answers
153 views

MLWE (and RLWE) to LWE reductions proof

In crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?
5
votes
1answer
285 views

How the condition $s \geq 8$ is determined in Lindner-Peikert cryptosystem?

In Lindner & Peikert paper, the authors propose that to set the cryptosystem's parameters, one should choose $q$ to be large enough to allow for a Gaussian parameter $s \geq 8$. My question is, ...
5
votes
1answer
100 views

What is the difference between Poly-LWE and Ring-LWE?

I am often confused by Poly-LWE and Ring-LWE, always thinking that they are different names for the same thing. In some literature, Poly-LWE is a simplified version of Ring-LWE? What is the difference?...
5
votes
0answers
1k views

How to explain Learning With Errors? [closed]

I am trying to understand this concept of Learning With Errors. There does not seem to be a layman explanation of it anywhere. Here I describe layman as someone who understands ML concepts a bit (non ...
5
votes
0answers
309 views

ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc

While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
4
votes
2answers
141 views

Hardness of LPN problem with small secret

The Learning Parity with Noise (LPN) assumption states that, for a fixed secret $s$ chosen uniformly from $\{0,1\}^n$, then the distribution that outputs $(a,a\cdot s+e)$, where $a$ is uniform in $\{0,...
4
votes
1answer
168 views

Minimum distance between polynomials in ring-LWE

Let $R_q=\mathbb{Z}_q[x]/\langle f(x)\rangle$ where $f(x)=x^n+1$, as in the ring-LWE problem. Let $a(x)$ be chosen uniformly at random from $R_q$. Question: Is there any theorem that lower bounds ...
4
votes
1answer
52 views

Is Type I lattice trapdoor hard to find even given oracle access to compute inverse of trapdoor function?

Consider the Type I lattice trapdoor in [GPV08]: https://eprint.iacr.org/2007/432.pdf Suppose a PPT adversary is given the LWE trapdoor function in the picture: $g_{A^\top} (s,e) = A^\top s + e = b (...
4
votes
2answers
192 views

what does output parameters of lwe estimator stands for?

I want to use lwe estimator to find classical and quantum security of my proposed key exchange protocol. On this website, I want to understand the output of sage code on lwe estimator given bellow. ...
4
votes
1answer
273 views

Why does Learning With Errors require a bunch of samples?

Solving Learning with Errors(LWE) with average case complexity is as hard as solving the SVP with worst case complexity. LWE requires $n$ dimensional lattice and $m$ samples of it, and Decisional-LWE ...
4
votes
1answer
112 views

LWE secure with one entry without noise

I'd like to know, is Learning With Error (LWE) (with modular noise) "secure" if one entry has no noise? More precisely, I have: a random matrix $A \in \mathbb{Z}_q^{m \times n}$ a random string $s \...
4
votes
1answer
187 views

Adapting LWE Trapdoors for Ring-LWE

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE. Theorem 5.1: There is an ...
4
votes
1answer
235 views

Decision-LWE to Search-LWE

Regev requires $q$ to be prime on lemma 4.2 of his paper for LWE. Why does he require that and how this effect the proof of lemma 4.2?
4
votes
0answers
36 views

How can I geometrically understand LWE ciphertext and decryption step?

In the bottom of the wikipedia article of LWE (https://en.wikipedia.org/wiki/Learning_with_errors), we can see construction of Public-key cryptosystem based on the LWE. But, I cannot understand whole ...
3
votes
2answers
443 views

Distribution of the Difference of Uniformly Random Elements

In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (...
3
votes
1answer
230 views

Pseudorandomness of ring learning with errors

My question is in Ring Learning with Errors, let $a(x)\in \mathbb{Z}_q(x)/(X^n+1)$ where $n$ is a power of $2$, be a random polynomial, $s(x),e(x)\in \mathbb{Z}_q(x)/(X^n+1)$ are the secret and error ...
3
votes
1answer
878 views

Parameters for LWE

In the LWE problem there are two methods in order to choose secure parameters. The Lindner-Peikert and Micciancio-Regev method. The first method is an attack to BDD : find closest vector knowing the ...
3
votes
1answer
101 views

Why don't we use an Extendable Output Function to efficiently store the public key of Regev's LWE-based encryption scheme over standard lattices?

In LWE-based schemes the public key is generated by choosing a random matrix (or polynomial) $A$, and outputting the pair $(A, b = A\cdot s + e)$, where $s$ and $e$ are vectors/polynomials with ...
3
votes
1answer
194 views

Security estimation of LWE using “On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL”

I recently found this paper eprint which estimates security of LWE instantiations using an improved Dual attack. However, I got confused looking at their example in this site. For example, in the case ...
3
votes
1answer
57 views

Replay attacks and LWE

Just a small question. Since in LWE the error is rather small, is there a problem with replay attacks? What I mean is that if we use the typical scheme of Regev [1] to encrypt a vector m, but this ...
3
votes
2answers
111 views

Ring-LWE in other fields

Can someone please tell me why in R-LWE we always make use of Cyclotomic fields, and specially those with degree equals to a power of $2$? Can we use another fields without losing in hardness of the ...
3
votes
1answer
78 views

Hardware Gaussian random numbers for lattice-based cryptography

I have been recently reading about lattice-based cryptography. I read that a key aspect of such protocols rely on added Gaussian noise on lattices, and which therefore require highly efficient and ...
3
votes
1answer
86 views

Randomness of Decision Learning With Error Problem

I read the statement of the Decision Learning with error problem is: distinguish between $(\vec a, \langle \vec a, \vec s \rangle + e)$ from uniformly random samples. Can anyone explain what does ...
3
votes
1answer
301 views

CCA2-secure encryption based on LWE/Ring-LWE

As I understand it, cryptosystems based on LWE/Ring-LWE are typically only IND-CPA, and fail to satisfy IND-CCA2. In fact, it appears that chosen ciphertext attacks could allow secret key recovery (!)...
3
votes
1answer
88 views

Is there an adaptive version of LWE assumption with respect to some potentially non-uniform secret distribution?

There is a version of LWE assumption as follow. Assume that there is a positive number $n$, an integer $q = q(n) \geq 2$, an error distribution $\chi = \chi_{n}$, a vector $\mathrm{\mathbf{s}} \gets \...
3
votes
1answer
185 views

Encoding of the message in Regev encryption

In public key encryption from LWE, we do the following steps $\textbf{PKE.KeyGen($1^n$)}$ takes as input the security parameter n, samples $A \leftarrow \mathbb{Z}_p^{n \times m}$ and $\textbf{e} \...
3
votes
1answer
167 views

R-LWE instantiation with non-power of 2 polynomial

In almost all RLWE papers, the polynomials are chosen from a ring $\mathbb{Z}[x]/f(x)$ where $f(x)$ is a polynomial of the form $f(x)=x^{2^n}+1$. That leaves us the choice of polynomials like $x^{256}+...
3
votes
0answers
42 views

Choosing the Bernoulli distribution for LPN encryption scheme

The symmetric-key encryption scheme from [1] is based on the LPN (learning parity with noise) problem. The definition of the problem is, informally, that the adversary cannot recover $\mathbf{s}$ from ...
3
votes
0answers
62 views

Does secure LWE implementation leak bit information?

We know RSA leaks one bit about the factors and improper yet secure implementations of Discrete Logarithm leak one bit about the discrete logarithm. Does LWE leak any information?
3
votes
0answers
88 views

LWE status versus modern deployed crypto [closed]

LWE is the one of the most promising post quantum strategy. How does parameters (key sizes, time for encryption etc) for LWE compare with modern deployed standards such as Factoring or discrete log ...
2
votes
2answers
69 views

LWE versus neural nets

It seems like that the construction of the LWE problem: $As + e = b$ resembles how neural nets work: $Ax + b = y$. In LWE, we are given the problem instance $A$, and the product with errors $b$ and ...
2
votes
1answer
182 views

Threshold decryption in multi-key homomorphic encryption

I have a problem understanding the security of threshold decryption in multi-key homomorphic encryption (MKHE) with so called "noise flooding". In particular I think that it is not secure, so probably ...
2
votes
1answer
138 views

A query on Learning with errors(LWE) problem

In generating an LWE sample, we do $s\xleftarrow{$}\mathbb{Z}_q^{n}, A \xleftarrow{$}\mathbb{Z}_q^{n \times m}~$and $e\xleftarrow{$}\mathbb{{\chi}^{m}}$ Then we compute $b^T$ = $s^TA$ + $e^T$ and ...
2
votes
1answer
175 views

A Simple Provably Secure Key Exchange Scheme Based on the LWE

In this paper (A simple provably secure key exchange by Ding et al.), I am trying to understand the correctness (which is given on page number 8) of the key exchange technique based on LWE. To ...
2
votes
1answer
43 views

Security of somewhat homomorphic encryption via LSB encoding?

I'm reading this paper https://eprint.iacr.org/2011/344.pdf It says that "The secret-key encryption scheme whose security is based on the LWE assumption is rather straightforward. To encrypt a bit, $...
2
votes
1answer
126 views

Probability distribution function in Regev Cryptosystem

In Regev - On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, chapter 5, Public Key Crypto System, it is stated that The probability distribution function $\chi$ is taken to ...
2
votes
1answer
67 views

Decrypting message as MSB in regev scheme

I was watching this FHE video and it define Regev encryption scheme as fallow : kyegen: sk : choose $t = (1,s)^t \in \mathbb{Z}_q^{n+1}$ pk = $A \in \mathbb{Z}_q^{m*(n+1)}$ random except $[A * t]_q$ ...
2
votes
1answer
100 views

Interpreting Figure 1 in the “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography”

I'm reading "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography" by O. Regev. I'm having trouble with understanding graphs in Figure 1. By the definition of $\overline{\psi}_{\...
2
votes
0answers
40 views

Rounding function used in Saber Key Exchange

In Saber: Module-LWR based key exchange, the authors use a rounding function called $\textit{bits}$, defined (in page 3) as follows: $bits(x, i, j)$, with $j \leq i$, gives $j$ consecutive bits of a ...