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
15 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
75 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
57 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
38 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
37 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
112 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
166 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
  • 63
0 votes
0 answers
51 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
186 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
35 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
21 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
95 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
135 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
115 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
112 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
150 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
111 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
483 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
211 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
2 votes
0 answers
40 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
46 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
35 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
  • 367
3 votes
0 answers
45 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
  • 383
2 votes
1 answer
71 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
  • 383
2 votes
1 answer
146 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
2 votes
0 answers
85 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
  • 21
2 votes
2 answers
415 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
59 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
55 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
41 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
  • 21.9k
3 votes
1 answer
203 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
83 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
128 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
190 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
404 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
103 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
  • 360
3 votes
1 answer
314 views

Why is the best way to solve LWE (and Cryptographic related Systems) with SVP (approx)?

Community, I'm new into lattice based cryptography, and I'm interested about the security of cryptography schemata like Kyber and why the focus of solving this problem lead into solving approx. SVP. ...
Max Weber's user avatar
3 votes
2 answers
505 views

Break Lattice-Based Cryptography with Variational Quantum Algorithm (only 25 k. Qbits for Kyber1024)?

I am currently writing a seminar paper on Kyber and other lattice-based methods. I was so excited about the lattice-based methods that I also currently searched quantum algorithms to solve the methods....
Max Weber's user avatar
1 vote
0 answers
61 views

Why the error in LWE is sampled from the normal distribution?

$$a_1*s+m_1+e_1 = b_1\\\cdots\\ a_n*s+m_n+e_n = b_n$$ The LWE problem is related to finding the solution $s$ to this system, when the $e$ are sampled from the normal distribution. Why the normal ...
Rafaelo's user avatar
  • 23
1 vote
1 answer
90 views

Decryption analysis for Regev's Public Key Cryptosystem

Regev's Public Key Cryptosystem is defined as follows: I want to proof the correctness. For this it must be shown that a 0 is decoded correctly and equally that a 1 is decoded correctly. I would ...
P_Gate's user avatar
  • 393
1 vote
1 answer
92 views

Derive probability estimation for 'learning from parity with error'

In Regev's Paper "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography" he considers in the introduction of the paper the "learning from parity with error". ...
P_Gate's user avatar
  • 393
1 vote
1 answer
196 views

LWE encryption error

in learning with error encryption scheme (e.g. in Kyber scheme). there are two vectors: $u = r^t A + e_2$ and $v= r^t * pk + e_3 + \lfloor \frac{q}{2}\rceil m$ such that $pk = As +e_1$. my question ...
Don Freecs's user avatar
0 votes
0 answers
87 views

Cryptographic functions as feature map/kernel function?

Has there been any use of cryptographic function as a kernel function with support vector machine? There are several standard kernels to be used with SVMs each with its own scenario. I was not able to ...
Omar Shehab's user avatar
2 votes
0 answers
99 views

Regev PKE not CPA secure for specific $A$?

I encountered notes stating that, for certain fixed $A$, such as $A \in M_{n\log(q)\times n}$ as follows: \begin{bmatrix} 1 & 0 & 0 &\dots\\ 2 & 0 & 0 &\dots\\ 4 & 0 & ...
Anon's user avatar
  • 383
2 votes
1 answer
106 views

Statistical Distance and Learning with Rounding

Given an integer $b$ modulo a prime $q$, one can define a `rounding’ function $\lfloor b\rceil_p$ for a prime $p$, $p<q$, as follows: $$\lfloor b\rceil_p = \lfloor \frac{p}{q}\cdot b\rceil\bmod p.$$...
a196884's user avatar
  • 381
1 vote
1 answer
80 views

Type 1 Trapdoor Sampling in LWE

In the BGN-like LWE cryptosystem, section $2.2$, we sample a $m \times m$ trapdoor matrix $T$ that is full rank such that $TA = 0 \pmod q$. Suppose that $q$ is prime so we are in a finite field: if $T$...
pizzamath's user avatar
4 votes
1 answer
211 views

Finding the exact solution of an LWE instance with a sparse matrix

I already asked a question about the feasibility of LWE when the matrix A is sparse or small here. Let $q$ be a prime, let $\chi$ be a distribution of $\textit{small}$ elements over $\mathbb{Z}/q$, ...
Kolja's user avatar
  • 133
1 vote
0 answers
82 views

LPN over non-binary fields

With regard to LPN over non-binary fields like $\mathbb{F}_3,\mathbb{F}_5,\cdots$, are there any studies about that ? We also would like to know any articles that have a formal definition of the non-...
mathcat's user avatar
  • 11
2 votes
0 answers
107 views

SIMD mode for RGSW encryption?

I know schemes like BFV, BGV, and CKKS supports SIMD operations where the plaintext is vector of values instead of polynomial. I am wondering if RGSW/TFHE kind of schemes can also support SIMD ...
LWE-13's user avatar
  • 251

1
2 3 4 5