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
0 votes
0 answers
158 views

Is the cryptography scheme over lattice still secure? [duplicate]

In https://eprint.iacr.org/2024/555, the author proposed a quantum algorithm to solve LWE problem. How serious is its impact on the existing scheme over lattice.
guangyu liao's user avatar
35 votes
0 answers
4k views

Polynomial-time Quantum Algorithms for Lattice Problems

A new paper, by Yilei Chen, whose title is Quantum Algorithms for Lattice Problems (https://eprint.iacr.org/2024/555) appeared on eprint and it claims to solve hard lattice problems, such as the ...
Hilder Vitor Lima Pereira's user avatar
2 votes
1 answer
54 views

The necessity for lattice reduction in LWE

I am trying to understand how exactly lattice reduction and LWE are linked. The attacks on LWE I have seen all use lattice reduction in some way or another, dual attacks, uSVP type and so on. Naively, ...
nnolte's user avatar
  • 121
0 votes
1 answer
45 views

The proof of Claim 5.2 in the "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography"

When I'm reading this paper "On lattices, learning with errors, random linear codes, and cryptography" by O. Regev. I have trouble understanding the proof of claim 5.2. "Hence, it is ...
Solaris's user avatar
2 votes
1 answer
208 views

Ring Learning With Errors : why is it called ring and referred it as Ring LWE

I am curious about the structure of the quotient ring in Ring LWE. So $R=\mathbb Z_q[x]/(x^n+1)$, where q is prime, $x^n+1$ is an irreducible polynomial and $n$ is a power of 2. So, this structure ...
user479610's user avatar
0 votes
1 answer
45 views

What does it mean the "Distinguisher" in LWE decision version?

As we know in block ciphers, the distinguisher means that despite thousands ciphertexts (and plaintexts), allows an attacker to distinguish the encrypted data from random data. This attack is ...
R_Jalaei's user avatar
  • 141
3 votes
0 answers
54 views

Why the unreasonable effectiveness of simple brute-force attack on LWE Lattice Secret Key?

Exploring LWE Lattice crypto. Generate system matrix and secret key from cryptographic PRNG (Fortuna). Derive public key as |p> = A|s>, then add NBits of zero mean uniform noise to the public ...
DBM's user avatar
  • 157
1 vote
0 answers
79 views

Digit Extraction for HE Bootstrapping

I was wondering if someone could explain the Digit Extraction from HElib in simple words: Apply a homomorphic (non-linear) digit-extraction procedure, computing $r$ ciphertexts that contain the ...
kindi's user avatar
  • 11
3 votes
2 answers
132 views

Connection between (noisy) CVP and LWE

What's actually the difference between a (noisy) CVP and LWE? It seems to me that both are the same. With the definition of LWE: $$A * s + e = b$$ solving for secret vector s is the same than solving ...
lstk44's user avatar
  • 73
1 vote
1 answer
101 views

Decision LWE vs Search LWE: Which one is harder?

Sometimes if we have an attacker who's able to solve decision-LWE problem then we can use them (as a sub-routine) to solve (search) LWE problem, i.e., $\mathsf{sLWE} \leq \mathsf{dLWE}$. Conversely, ...
user1035648's user avatar
1 vote
0 answers
20 views

Search the LWE problem

When designing the search LWE problem, how do you set the dimensions of the A matrix? Or under what circumstances can I use very few matrix dimensions to achieve 128-bit security? Up to noise level? ...
Caimei Wang's user avatar
2 votes
1 answer
53 views

Learning the LWE secret with advice

I am trying to argue about the hardness of LWE, but in a setting that is different from the standard one. Consider the task of learning the LWE secret $s$ from noisy samples. The specifications of the ...
BlackHat18's user avatar
2 votes
1 answer
179 views

Do we know that LWE is harder than Ring LWE?

The plain, normal-form, decisional LWE problem over $\mathbb{Z}/q\mathbb{Z}$ is: given a uniformly random $n\times n$ matrix $A$ and vector $b\in \mathbb{Z}/q\mathbb{Z}^n$, decide if $b=As+e$ for ...
Sam Jaques's user avatar
  • 1,137
0 votes
0 answers
17 views

[error reducing techinique in lattice based commitment]

I am aware there are many techniques to reduce the error of lattice-based homomorphic encryption. But is there any technique to deal with lattice-based homomorphic commitment, e.g., More Efficient ...
js wang's user avatar
  • 327
0 votes
1 answer
91 views

Primal attack On Kyber algorithm specifications

In the Kyber Algorithm specifications document, chapter 5.1.2 primal attack, it says that: Given the matrix LWE instance $(A,b=As+e)$, one builds the lattice $\Lambda = \{x\in \mathbb{Z}^{m+kn+1}:(A\...
qiuxicj's user avatar
1 vote
1 answer
59 views

in Homomorphic Encryption Standard, why in the LWE increasing security level yields smaller ciphertext?

I am currently reading Homomorphic Encryption Standard. May I ask that for table 1 in the link, why increasing the security level will yield a smaller ciphertext size (log q)? I attach a screenshot ...
js wang's user avatar
  • 327
0 votes
0 answers
51 views

[About choosing params in BGV like ciphertexts]

I am new to lattice-based cryptography, so sorry that this question might seems stupid May I ask that how can I choose the BGV parameter of ciphertext with plain text in mod 128, and error in ...
js wang's user avatar
  • 327
1 vote
1 answer
64 views

How to set the variance of LWE when using the lwe estimator

based crypto And I would like to use the lwe estimator to calculate bound for ring LWE Found in this issue It seems to me I can set up parameters like params = LWE.Parameters(n=2^14, q=2^438, Xs = ...
js wang's user avatar
  • 327
1 vote
2 answers
131 views

About multiply by constant of LWE

I am new to lattice-based cryptography May I ask that for a lattice-based encryption $$enc(m) = A^{T}R+m \bmod q$$ If I set the $q$ to be able to decrypt to $m$ (and suppose the bound of $q$ is tight ...
js wang's user avatar
  • 327
4 votes
2 answers
189 views

As a high level intuition, why is LWE without modular reduction easy to solve?

The LWE conjecture states that, given $A \in \mathbb{Z}_q^{m \times n}$ and $A x + e$ for $x \in \mathbb{Z}_q^n, e \in \mathbb{Z}_q^n$ it's difficult to recover $x$, given that $e$ is sampled from a ...
marmistrz's user avatar
  • 143
0 votes
0 answers
38 views

What are the implications for the proof when we substitute matrix multiplication with a bitwise XOR operation in Definition 5.1 (LWE degree-k PRF)?

In the paper located at https://eprint.iacr.org/2011/401.pdf, suppose we replace matrix multiplication with bitwise XOR operations in Definition 5.1 to create an LWE degree-k PRF. I'm seeking ...
DP2040's user avatar
  • 73
0 votes
0 answers
63 views

Understanding noise budget calculation in seal

I am trying to understand theory behind noise budget operation implemented in seal Let the ciphertext be defined as $$ c0=A \in Rq \\c1= As+v+delta*m \in Rq $$ They first calculate noise ...
LWE-13's user avatar
  • 251
3 votes
1 answer
226 views

LPN Encryption Homomorphism

Trying to understand the LPN encryption in this paper: https://eprint.iacr.org/2021/120.pdf. From Definitions 4 and 5, ciphertext is $c=C\cdot s\oplus e\oplus G\cdot m$ and the paper says the LPN ...
alexander's user avatar
  • 149
1 vote
0 answers
41 views

[About parameters effect LWE and SIS to be computation or perfect secure]

Hello I am new to lattice cryptography I am reading the paper More Efficient Commitments from Structured Lattice Assumptions They define bound B in page 3 Then In figure 1 in page 9 Can ...
js wang's user avatar
  • 327
1 vote
0 answers
22 views

Non-Gaussian distribution in continuous learning with error

The CLWE problem (and related) talks about the hardness of finding the secret key $\vec{s}$, given polynomially many samples $(\vec{a},t)$, where $\vec{a}$ is sampled from the normal distribution, and ...
Jim Haddocc's user avatar
1 vote
1 answer
134 views

learning with errors

If I talk about efficiency of system of learning with error, is it it fine for q to be composite in Z_q, the ring of integers. As when q would not be prime, Z_q will not be field anymore, won't it ...
user479610's user avatar
2 votes
1 answer
172 views

Why use small error vectors in LWE instead of big ones?

In LWE systems, why is it recommended to add only small error vectors to the system of equations and not big error vectors? Can someone come up with an example?
user479610's user avatar
1 vote
2 answers
143 views

LWE assumption in cryptographic applications

The LWE assumption states that it is hard to distinguish LWE samples from uniformly distributed samples. That is, the distinction $(A,b)$ with $A$ and $b$ uniformly distributed, is hard to distinguish ...
Zpeed78's user avatar
  • 95
4 votes
2 answers
196 views

LWE and distributions

In LWE, the error term $e$ is "classically" obtained from the discrete normal distribution. Why is it so often found that this distribution is used? Are there other possibilities for ...
Zpeed78's user avatar
  • 95
2 votes
1 answer
166 views

Learning with Errors Naive Algorithm

In Regev's publication "The Learning with Errors Problem", a naive algorithm is given on page 3 that can be used to tackle the LWE problem. This is the statement: Another, even more naive ...
Zpeed78's user avatar
  • 95
0 votes
2 answers
149 views

Is $0/1$ error ok in LWE? [closed]

Can the error in LWE or ringLWE schemes be from $\{0,1\}$? If not why and what is the best attack in this case?
Turbo's user avatar
  • 908
1 vote
1 answer
503 views

Challenges like RSA factoring challenge

RSA factoring challenge is a famous one and is still not completely solved. Are there similar challenges for Discrete log over $\mathbb Z_p^*$? Discrete log over Elliptic curves? LWE? LPN?
Turbo's user avatar
  • 908
0 votes
1 answer
237 views

What if LWE is not as secure as we think?

LWE schemes are currently being deployed. LWE has no quantum polynomial time algorithms as far as we know. Despite this what is the consequence if LWE can be broken on a classical computer? Do we ...
Turbo's user avatar
  • 908
3 votes
1 answer
77 views

Ring LWE distribution definitions

This may be a stupid question but I've been stuck on parsing these definitions for a while. I am reading the paper "On Ideal Lattices and Learning with Errors Over Rings" by Lyubashevsky, ...
cryptolearner's user avatar
1 vote
0 answers
47 views

Tensor and power bases for SIS?

What is there to say about using a power basis or a tensor basis or some combination of them for the RSIS problem in lattice cryptography? Restricting to dimension 3 for illustration, usually the ...
Joseph Johnston's user avatar
1 vote
1 answer
38 views

LWE KEMs and message coding

In many proposed lattice PKE schemes, the plaintext is encoded or modulated in a simple fashion, e.g. using Kyber-ish notation: key gen: $pk=(A, t=As+e)$, $\quad sk=s\quad$ ($A$ random, $s$, $e$ ...
yoyo's user avatar
  • 421
3 votes
0 answers
47 views

What are the advantages of coding based cryptosytems over LWE (Regev)?

Having recently learned of coding based cryptography, it seems that they key size for post-quantum security might be a lot larger than what is required by Regev PKE (in the former keys include several ...
Anon's user avatar
  • 403
2 votes
1 answer
116 views

What is the relation between LWE and coding based cryptography?

I've recently heard about coding based cryptography and it seems very close to the LWE assumption in that it is based on the idea that the error is hard to identify. They are both post-quantum schemes ...
Anon's user avatar
  • 403
2 votes
1 answer
148 views

Is there a version of LWEEncrypt in which probability of decryption error is zero?

Is there modification to LWE public key crypto-system which makes the decryption process is totally deterministic and does not affect security?
Ali Haktan German's user avatar
3 votes
0 answers
116 views

Hardness of LWE with Uniform Secrets and Error Distributions

I have seen various papers discussing the security of the Learning with Errors problem with very small uniform secrets and errors but I have not found any papers on the general LWE problem with ...
Marco's user avatar
  • 31
2 votes
2 answers
508 views

In Learning with errors, what is the relation between the size(or standard deviation) of errors and security?

I want to understand how the hardness of Learning With Errors problem varies as size of the error term changes. For example, assuming that the other parameters are the same, LWE with errors sampled ...
Lee Seungwoo's user avatar
1 vote
1 answer
73 views

LWE encryption: Errors for encrypted messages

I am following this paper Encryption from Learning with Errors for the generation of errors e1 and e2 to retrieve the ciphertext u and v as described below. ...
user108142's user avatar
1 vote
1 answer
64 views

LWE Decryption: Generating errors for (c1, c2) that match binary message m

In the encryption process, the ciphertexts c1 and c2 are added to errors e1 and ...
user108142's user avatar
2 votes
0 answers
45 views

Learning with rounding: uniformity

Naively, when one applies rounding to a uniform random value one anticipates that the change is uniformly distributed. In lattice-based cryptography, is there a formal notion or proof of equivalence ...
Daniel S's user avatar
  • 23.8k
4 votes
1 answer
292 views

Understanding RLWE Encryption

LWE Encryption Scheme by Regev is inefficient due to its public key sizes in $O(n^2)$. This led to the variant problem RLWE, defined in this paper : Let $n$ be a power of two, and q a prime ...
rerouille's user avatar
0 votes
1 answer
97 views

Unable to retrieve the binary string using LWE and Lattice-based decryption

I am new to this encryption scheme, so I may not be exactly sure of its implementation. I have a list of (u, v) ciphertext pairs to decrypt, each of them are 1-bit. ...
user108142's user avatar
1 vote
1 answer
173 views

Why predicting an error in Crystal Kyber is considered to be hard?

Hi I have started studying on crystal kyber recently. Gained some knowledge regarding its algorithm and how it works. My doubt is why it is tough for attacker to extract secret vector from pk itself ...
Rakmo's user avatar
  • 21
3 votes
1 answer
208 views

Hardness of LWE

I was reading "TFHE Deep Dive" from Ilaria Chillotti, and I am a bit confused over the sample given in 31:08 In the above toy sample, isn't it possible to directly eliminate noise by ...
xade93's user avatar
  • 51
3 votes
1 answer
515 views

CRYSTALS-KYBER versus FrodoKEM, what makes each of them different than the other?

NIST's main recommendation for encryption/decryption mechanism is CRYSTALS-KYBER. Whereas, the BSI (German equivalent) chooses FrodoKEM. As far as my knowledge goes both these mechanisms use LWE ...
Chirag Parmar's user avatar
4 votes
1 answer
114 views

"Shifting" a dual-Regev keypair away from a trapdoored instance

This question pertains to identity-based key encapsulation mechanisms (IB-KEMs). To recap the functionality: $\mathsf{KeyGen}(1^\lambda) \to (\mathsf{msk}, \mathsf{mpk})$ Generates the master keypair ...
rozbb's user avatar
  • 390

1
2 3 4 5