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
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?
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 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}+...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ~~...
user avatar
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.
user avatar
  • 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 ...
user avatar
  • 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{...
user avatar
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_{...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
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 ...
user avatar
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? ...
user avatar
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 ...
user avatar
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
user avatar
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 ...
user avatar
  • 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}...
user avatar
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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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_\...
user avatar
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 ...
user avatar
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 ...
user avatar
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.
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
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}, \...
user avatar
  • 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)...
user avatar
  • 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$. ...
user avatar
  • 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 ...
user avatar
  • 803