# 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).

80 questions
Filter by
Sorted by
Tagged with
12 views

### Security of LWE when a small leakage is allowed on the noise

Short version: Is there some results that are known on the security of the Learning With Error problem when there are some leakages, notably on the noise? (In my case these leakage come from a bit ...
348 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 ...
52 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  to encrypt a vector m, but this ...
125 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?
27 views

42 views

### Multibit LWE Encryption

What's the simplest way to encrypt multiple bits with LWE public key cryptosystem? Some paper say use a different secret key for each bit of the message. Does that mean the length of the message ...
36 views

### learning with errors is hard even when given some information about the secret vector

In this case we are given the distribution D from which secret s is sampled. If I can get some hints to proceed with the questions, it would be of help. Thanks,
92 views

40 views

### Solving for secret s in LWE problem

in LWE instance $b=A^t s +e$, can we find an orthogonal basis of coefficient matrix A in polynomial time, let it be B.Multiply B to get $Bb=Be$ as term with s will vanish. Then solve for $e$. After ...
87 views

102 views

127 views

### Refreshing Procedure in FHEW: membership test

I am facing an issue regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second. It concerns the MSBextract algorithm during the refresh procedure. Especially, they ...
180 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 ...
398 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 ...
167 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 ...
44 views

### Gate count for Ring-LWE

In one of my recent research, I need to compare the number of gates needed in Ring-LWE encryption to AES in the circuit model. For AES we can find some estimation like this site, but for Ring-LWE we ...
180 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 ...
123 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 ...
155 views

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 ...
211 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?