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).
202
questions
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 ...
- 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\...
- 3
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 ...
- 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 ...
- 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 = ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 111
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 ...
- 63
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?
- 63
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 ...
- 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 ...
- 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 ...
- 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?
- 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?
- 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 ...
- 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, ...
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 ...
- 357
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$ ...
- 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 ...
- 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 ...
- 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?
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 ...
- 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 ...
- 363
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.
...
- 31
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 ...
- 31
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 ...
- 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 ...
- 41
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.
...
- 31
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 ...
- 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 ...
- 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 ...
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
...
- 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.
...
- 65
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....
- 65
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 ...
- 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 ...
- 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". ...
- 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 ...
- 421
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 ...
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 & ...
- 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.$$...
- 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$...
- 11
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$, ...
- 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-...
- 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 ...
- 251