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).
143
questions
1
vote
1
answer
44
views
Errors for $\mathsf{LWE}$
Why do we take Gaussian-like errors in $\mathsf{LWE}$?
Why for example we don't take uniform errors?
- 345
0
votes
1
answer
25
views
Solving $\mathsf{SVP}_{\gamma}$ in worst-case
What does it mean to solve $\mathsf{SVP}_{\gamma}$ in worst-case?
Does it mean that the problem is solvable for any lattice we choose?
- 345
0
votes
1
answer
37
views
How to understand noise growth in BFV?
I am trying to understand the noise growth due to multiplication in BFV encryption.
As explained in section 4 and equation 3 of this paper: https://eprint.iacr.org/2012/144.pdf.
I couldn't follow what ...
- 197
4
votes
1
answer
143
views
What is the effect of low rank dual sublattices on the dual lattice attack on LWE?
In the dual lattice attack of Espitau, Joux and Kharchenko (On a dual/hybrid approach to small secret LWE), the authors propose distinguishing (and subsequently recovering secret values) of LWE ...
- 9,576
0
votes
1
answer
55
views
Computational indistinguishability of two LWE type samples
Consider the problem of distinguishing between polynomially many samples of either
\begin{equation}
(x, b, As + e) ~~\text{or}~~\left(x, b, ~Ax + b\cdot(As + e) + e'\right).
\end{equation}
Here, $A$ ...
- 3
1
vote
1
answer
62
views
How lattices and LWE are connected?
I am a last-year master student in pure mathematics and I am working on my thesis. I am working on a connection between lattice-based encryption and Ring LWE and between Ring LWE and Homomorphic ...
1
vote
1
answer
35
views
What is Relationship between ciphertext quotient and polynomial degree in RLWE?
In Ring Learning with Errors problem, the size of the ciphertext quotient $q$ decides the size of the polynomial degree $n$ or vice versa. In other words, rlwe problem is hard only when the polynomial ...
- 197
1
vote
1
answer
59
views
Questions on LWE with a repeated secret matrix S
Consider a formulation of LWE where we are given either $(x,S x+e)$ or $(x,u)$ --- where $S$ is an $m \times n$ secret/hidden matrix, $x$ is a randomly sampled $n \times 1$ vector, $e$ is an $m \times ...
- 285
0
votes
1
answer
62
views
LWE-search to SVP reduction
So for my diploma thesis I'm writing about Regev's LWE cryptosystem from his original 2005 paper. I'm done with with correctness and security (only reduction from LWE-search via average-to-worst and ...
- 11
3
votes
2
answers
67
views
LWE with the matrix A repeated
Consider the following version of Learning With Errors.
You are either given $(A, As_1 + e_1, As_2 + e_2, \ldots, As_k + e_k)$ or $(A, u_1, u_2, \ldots, u_k)$, where
$A$ is an $m \times n$ matrix ...
- 285
1
vote
2
answers
65
views
Why RLWE is lighter than LWE and why we can pick $a_i$ as a permutation of $a_1$ in RLWE but not LWE?
In LWE, we have
$$<a_1,s> + e + \mu_1\in \mathbb{Z}_q$$
for a secret key $s\in \{0,1\}^n$ and $a_1\in \mathbb{Z}_q^n$
This is an encryption of a number $\mu_1$. If we want to encrypt $n$ ...
1
vote
1
answer
49
views
How to prove reduction from decision to seach LWE?
I am new to cryptography, and trying to understand the concepts of LWE (learning with errors) formally. I will state my understanding of the definitions, which might be incorrect.
Definitions ...
- 145
1
vote
0
answers
78
views
Can we transform LWE symmetric encryption scheme into a commitment scheme?
In the LWE symmetric encryption scheme, a ciphertext encrypting a message $\mu \in \{0,1\}$ under the secret key $\mathbf{s} \in \mathbb{Z}_q^n$ is $(\mathbf{a}, \mathbf{b}=\mathbf{a} \cdot \mathbf{s}+...
- 11
2
votes
1
answer
101
views
Questions regarding the pseudorandom function construction of Banerjee, Peikert, and Rosen
I am trying to understand the following pseudorandom function constructed by Banerjee, Peikert, and Rosen in this paper, assuming the hardness of LWE. Consider the following LWE/LWR based pseudorandom ...
- 285
1
vote
1
answer
48
views
RLWE with invertible elements
Let $R = \mathcal{O}_K$ be the ring of ingtegers of $K$, where $K$ is an algebraic number field, and $q$ a modulus. Let $\chi$ be some error distribution used to sample an element $e$. A primal RLWE ...
- 349
2
votes
0
answers
28
views
Centrality of Gaussian distribution for LWE error
Consider the LWE problem.
Let $A$ be an $m \times n$ matrix, $x$ is an $n \times 1$ vector, $u$ is a $m \times 1$ vector, and $e$ is sampled from a Gaussian distribution.
We are given either $Ax + e ~~...
- 285
0
votes
0
answers
18
views
Number of samples in FrodoKEM
Why does the number of samples in FrodoKEM is $m \approx n$?
The paper is here.
- 345
0
votes
1
answer
36
views
A smaller modulus-to-noise ratio means more security in LWE
Let $\text{Adv}^{\text{DLWE}}_{n,m,q,\sigma}$ be the advantage of an attacker to distinguish LWE samples from uniform ones, where $m$ is the number of samples, $q$ the modulus and $\sigma$ the ...
- 345
2
votes
1
answer
81
views
LWE and extended trapdoor claw free functions
Let $q \geq 2$ be a prime integer. Consider two functions, given by:
$$f(b, x) = Ax + b \cdot u + e~~~(\text{mod}~q),$$
$$g(b, x) = Ax + b \cdot (As + e') + e~~~(\text{mod}~q),$$
where we have:
\begin{...
- 285
2
votes
1
answer
57
views
The significance of duals in RLWE
In an algebraic number field, an ideal $I$ in the ring of integers $\mathcal{O}_K$ has dual $I^\vee = \{x\in\mathcal{O}_K\text{ : }T_{K/\mathbb{Q}}(xy)\in\mathbb{Z}\text{ for all }y\in I\}$, where $T_{...
- 349
2
votes
1
answer
71
views
How is it legal to use a rounded Gaussian for LWE?
As far as I understood, in Regev's initial paper, the error distribution was first constructed as follows:
Then rounded in the following way:
Using this distribution, the reduction in the theorem ...
- 345
1
vote
0
answers
26
views
polynomial time reduction from SIS to decisional-LWE?
Is the claim "If there is an efficient algorithm that solves SIS, then there is an efficient algorithm that solves decisional LWE" is sufficient?
or,
Is the claim above is equivalent to the ...
- 11
2
votes
1
answer
68
views
LWE and pseudorandom functions
Consider the learning with errors problem. Assuming LWE (or a variant of LWE, like ring LWE) is hard for polynomial time algorithms, can we construct a family of pseudorandom functions from there?
- 285
2
votes
2
answers
85
views
LWE - Encrypting/Decrypting messages bigger than 1 bit
I'd like to know if LWE (and its variants: RLWE and MLWE) can cipher messages bigger than 1 bit. Is it possible? I didn't find any reference yet. Could you explain it to me or give some good ...
1
vote
0
answers
60
views
The relationship between root hermite factor and bit-security?
The root hermite factor corresponding to an bit-security level, such as 1.0045 corresponding to 128-bit security. What is the root hermite factor corresponding to 100-bit, 160-bit, 180-bit security?
...
- 41
0
votes
0
answers
23
views
How to estimate the parameter of a lattice signature scheme with lossy reduction?
The parameter of a lattice signature scheme DAZ19 with tight reduction can be choosed to make the underlying hardness problem intractable. How to estimate the parameter of a lattice signature scheme ...
- 41
3
votes
0
answers
43
views
parameter estimating in lattice signature scheme
when reading [BDLOP18], I run the lwe-estimator with the recommended parameters in Table 2 , but the result of hermite factor is 1.007, this result is bigger than the recommended hermite factor 1.0035
- 41
2
votes
2
answers
82
views
*-LWE equivalent of Diffie-Hellman $g^{x^2}$ vulnerability
In Is Diffie-Hellman less secure when A and B select the same random number? , the possibility of Diffie-Hellman key exchange producing identical peer keys and the vulnerability of it against passive ...
- 6,541
3
votes
0
answers
63
views
Is the scheme in LWE also valid in R-LWE?
One way of interpreting matrices in RLWE is that they are a subset of standard integer matrices that have special structure.
For example, rather than using a random matrix $A\in\mathbb{Z}_q^{n\times n}...
1
vote
0
answers
61
views
Equivalence between search-LWE and decision-LWE
Are there any constraints when it comes to proving that search-LWE and decision-LWE are equivalent? Should we assume that the module $q$ is prime when switching from one version to another?
Please ...
- 345
1
vote
1
answer
81
views
Why $q$ in LWE must be polynomial in $n$
I am wondering why the modulus $q$ in the LWE problem has to be polynomial in $n$.
Another question is whether one can take it to be an arbitrary integer instead of a prime number.
- 345
0
votes
1
answer
84
views
NTL: Solve the closest vector problem for non-square matrix using LLL/Nearest Plane Algorithm
Assume I have a matrix $A \in \mathbb{Z}^{m \times n}$, $m > n$, which forms a basis of a lattice. Given a vector target vector $t = Ax + e$, $t,e \in \mathbb{Z}^m$,$x \in \mathbb{Z}^n$, I want to ...
- 337
1
vote
1
answer
111
views
SIS vs LWE Problem
The Ajtai one way function is defined by
$$f_A(x)= Ax \; mod\; q $$ where the x $\in \{0,1\}^m$ and A $\in \mathbb{Z_q}^{n \times m}$. $f_A(x)$ is one way function ( Ajtai 96)
While the Regev One way ...
0
votes
0
answers
23
views
Is there a way to combine the Fuzzy extractor (or SS+ Ext) with state-of-art deep learning model?
I recently reviewed biometric authentication with deep learning model, and I found, in cryptography, the fuzzy extractor,FE (or secure sketch,SS, plus strong extractor) have solve this problem good ...
4
votes
1
answer
168
views
Prove that a small Ring-LWE secret is unique
I just want to know whether my proof is correct, which is about proving that if the Ring-LWE secret is small, then it is unique. Before giving my proof, here is a fact:
Fact 1: $\Pr [\Vert r \Vert_\...
- 105
0
votes
0
answers
56
views
Is my proof about uniqueness of ring-LWE secret correct?
Suppose that $n$ is a power of two, $q=3\pmod 8$, prime and $R=\mathbb{Z}[X]/(X^n+1)$. Denote $\Vert\cdot\Vert$ as the infinity norm in $R_q=R/qR$ on the coefficients of elements in $R_q$. The ...
- 105
2
votes
1
answer
109
views
Proof that (ring-)LWE secret is unique
I read Regev's paper in 2005 about Learning with Errors and he mentioned that the secret of a LWE sample is unique but I have not seen a proof of this claim. Can someone point me to a paper proving ...
- 105
0
votes
1
answer
84
views
Small modulus to noise ration in LWE implies better security
I don't quite understand why a smaller quotient between modulus $q$ and the noise's standard deviation implies better security against known attacks.
- 345
2
votes
1
answer
102
views
Parameters in RLWE
Let $n, q, \sigma$ be the polynomial degree($x^n+1$), coefficient modulo, and the standard derivation, respectively. I often see some parameters such as
For RLWE, we can use the CRT to decompose the $...
- 379
2
votes
1
answer
89
views
The error distribution in LWE
$\textbf{Continuous LWE}$ : $(\overrightarrow{a}, b)\in \mathbb{Z}_q^n\times \mathbb{T}$, where $\mathbb{T}=\mathbb{R}/\mathbb{Z}$, $b = \langle \overrightarrow{a},\overrightarrow{s}\rangle/q + e\mod ...
- 379
2
votes
0
answers
47
views
RLWE like problem
Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$.
Let $s \gets R_q$ be a ...
0
votes
1
answer
104
views
Why is the error in RLWE "smaller" than LWE?
In LWE, the standard deviation satisfies $\alpha p > 2\sqrt{n}$, when we consider the discrete LWE in $\mathbb{Z}_p$, then the rounded Gaussian has standard deviation $\alpha p$. But in RLWE, the ...
- 379
0
votes
1
answer
88
views
Joint distribution of RLWE samples
Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. We draw samples $s_i \gets R_q$ uniformly at random. Additionally, we define the error distribution $\chi$ as a discrete ...
2
votes
1
answer
55
views
Choosing rings for PLWE
In [ELOS15], the authors give an attack on RLWE, and claim that "the hardness of Ring-LWE is...
dependent on special properties of the number field" chosen; whereas, responding to prior ...
- 349
1
vote
1
answer
64
views
How to understand why an algorithm uses additive or multiplicative homomorphic
If we take the example of LWE (Learning With Errors) how does one know if it's homomorphic by addition or multiplication?
- 13
1
vote
0
answers
82
views
Choosing the parameters $n$ and $q$ in RLWE cryptography
The usual RLWE cryptographic constructions that I have read uses the parameters $n$ to be a power of two and $q$ a prime such that $q\equiv 1 \mod (2n)$. Do I understand it correctly that the reason ...
- 105
0
votes
0
answers
170
views
Is the error distribution in Learning with Errors (LWE), the discrete Gaussian distribution?
In $\mathbb{Z}$, the discrete Gaussian distribution is defined as $D_{Z,s}(x) = \frac{\rho_s(x)}{\rho_s(\mathbb{Z})}, x\in \mathbb{Z}$.
In LWE, $(\overrightarrow{a}, b = \langle \overrightarrow{a}, \...
- 379
1
vote
1
answer
74
views
Is the discretization of the Guassian distribution on torus still a discrete Gaussian distribution?
Let $\rho_s(x) = e^{-\pi x^2/s^2}$ be the Gaussian measures, then the discrete Gaussian distribution on $\mathbb{Z}$ could be defined as $D_{\mathbb{Z},s}(x) = \rho_s(x)/\sum_{n\in \mathbb{Z}}\rho_s(n)...
- 379
1
vote
1
answer
85
views
What if the bitlength of the value evaluated in Barrett reduction is greater than 2k the modulus?
For $c\equiv a \pmod n$, in Barrett Reduction, $\mu = \lfloor{\frac{2^{2k}}{n} \rfloor}$ is precomputed, where $k = \lceil{\log_2{n}} \rceil$ and the bitlength of $a$ is assumed to be less than $2k$. ...
- 11
2
votes
2
answers
332
views
Why does bootstrapping (R)LWE homomorphic encryption produce small noise?
Why does homomorphic evaluation of the decryption circuit produce a ciphertext with "fresh" or small noise?
Rough description of bootstrapping homomorphic encryption:
Suppose we have a ...
- 803