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
0answers
24 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? ...
0
votes
0answers
22 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 ...
3
votes
0answers
36 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
2
votes
2answers
65 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 ...
3
votes
0answers
40 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
0answers
45 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 ...
1
vote
1answer
70 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.
0
votes
1answer
49 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 ...
1
vote
1answer
44 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
0answers
21 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
1answer
141 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_\...
0
votes
0answers
50 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 ...
2
votes
1answer
84 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 ...
0
votes
1answer
60 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.
2
votes
1answer
70 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 $...
2
votes
1answer
68 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 ...
2
votes
0answers
45 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
1answer
82 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 ...
0
votes
1answer
82 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
1answer
45 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 ...
1
vote
1answer
53 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?
1
vote
0answers
69 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 ...
0
votes
0answers
132 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}, \...
1
vote
1answer
63 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)...
0
votes
0answers
31 views

What distribution is required to ensure the security of the RLWE?

In LWE, the error should be sampled from a discrete Gaussian distribution. Then, in RLWE, the error is a polynomial in $\mathbb{Z}_q[x]/(x^N+1)$, it could be sampled coefficient wise. However, when we ...
1
vote
1answer
58 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$. ...
2
votes
2answers
290 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 ...
0
votes
0answers
22 views

What does the "scale invariant" mean in some FHE schemes?

In some paper about FHE, the term "scale invariant" often appears. What does it means?
6
votes
2answers
317 views

LWE: Round a continuous Gaussian to a true Discrete Gaussian

Short version: how is it possible to round a continuous Gaussian into a true discrete Gaussian (usually denoted $\mathcal{D}_{\mathbb{Z},\alpha q}$)? The goal is to obtain a reduction from continuous ...
4
votes
1answer
137 views

LWE with identity sub-matrix and reused sampled from [MP12]: why is it secure?

I studied this paper a while ago, but now I'm confused by the paper Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller by Micciancio and Peikert. Page 24 and 25, they present an algorithm that ...
2
votes
1answer
84 views

Computational LWE-Trapdoor without tag

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Micciancio and Peikert mention that it is possible to save an additive $n$ term in the dimension $\bar{m}$ in paragraph $\...
3
votes
1answer
118 views

How small can the error be in LWE?

For modulus $Q$ and stddev $\sigma$, [GHS12] suggests that, to achieve 128-bit security, just choose the dimension $N$: $$ N\geq(Q/\sigma)\cdot 33.1 $$ This seems to suggest flexibility to choose ...
0
votes
1answer
77 views

Module LWE with an even modulus

Does module-LWE remains hard for an even modulus $q$, or a power of two? This is true for Ring-LWE (pseudorandomness) and Module-LWR (SABER). I can't find any reference to it!
0
votes
0answers
31 views

Is there a LPN estimator like LWE?

I recently studied the LPN problem and BKW algorithm for solving LPN problem. Several papers deal with the concrete parameters of LPN to be secure against BKW algorithm, but I cannot measure the ...
1
vote
0answers
41 views

Advantage of distinguishing LWE using short vector in dual lattice

In analyzing the advantage of distinguishing LWE via dual attack, many papers uses the result of [LP11] as follows : Given an LWE instance parameterized by $n$, $\alpha$, $q$ and a vector $\mathbf{v}$...
2
votes
1answer
115 views

Decrypting message as MSB in regev scheme

I was watching this FHE video and it define Regev encryption scheme as fallow : kyegen: sk : choose $t = (1,s)^t \in \mathbb{Z}_q^{n+1}$ pk = $A \in \mathbb{Z}_q^{m*(n+1)}$ random except $[A * t]_q$ ...
1
vote
0answers
44 views

Attacks on LWE when q is a power of 2

I am working on an LWE instance where q is a power of 2 and I'm wondering if there is any literature about attacks in this context, especially if there are any attacks which work significantly better. ...
1
vote
0answers
72 views

Solving RLWE modulo a prime ideal

Suppose you have the following set up for RLWE: $K$ is a cyclotomic field of degree $n$ over $\mathbb{Q}$, and $p\in\mathbb{Z}$ is a prime integer that splits as follows in $R = \mathcal{O}_K$: $p\...
5
votes
1answer
165 views

What is the difference between Poly-LWE and Ring-LWE?

I am often confused by Poly-LWE and Ring-LWE, always thinking that they are different names for the same thing. In some literature, Poly-LWE is a simplified version of Ring-LWE? What is the difference?...
0
votes
1answer
109 views

CKKS security estimation for Palisade

My question is rather practical and specific. I am trying to setup an efficient CKKS scheme in Palisade. To this end, the automatic choice for secure parameters has to be turned off and I rely on the ...
2
votes
1answer
97 views

Rounding function used in Saber Key Exchange

In Saber: Module-LWR based key exchange, the authors use a rounding function called $\textit{bits}$, defined (in page 3) as follows: $bits(x, i, j)$, with $j \leq i$, gives $j$ consecutive bits of a ...
1
vote
1answer
72 views

Can we possible to solve the LPN problem using Arora-Ge algorithm?

I recently studied how to solve the LWE (learning with errors) using algebraic relations proposed by Arora and Ge (paper : New Algorithms for Learning in Presence of Errors). As I understood, for LWE ...
2
votes
0answers
47 views

Security of LWE when a small leakage is allowed on the noise

Short version: Are there some results that are known on the security of the Learning With Error problem when there are some leakages, notably on the noise? (In my case these leakages come from a bit ...
8
votes
1answer
470 views

NewHope and NIST's Post-quantum standardization

Where can I find NIST's reasoning to eliminate NewHope from the 3rd round of the post-quantum competition? I see all the lattice KEMs finalists are based on modules. Is being a ring-based KEM ...
3
votes
1answer
67 views

Replay attacks and LWE

Just a small question. Since in LWE the error is rather small, is there a problem with replay attacks? What I mean is that if we use the typical scheme of Regev [1] to encrypt a vector m, but this ...
5
votes
2answers
345 views

MLWE (and RLWE) to LWE reductions proof

In crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?
1
vote
1answer
41 views

Guessing the Secret in RLWE Search-to-Decision

In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $s$, and using the guess to transform a sample from $\mathfrak{q}...
3
votes
2answers
482 views

Distribution of the Difference of Uniformly Random Elements

In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (...
1
vote
0answers
133 views

What are the prerequisites for understanding Lattice based Cryptography, LWE or RLWE based on SVP?

I'm new to Quantum Resistant Cryptography, so, I thought of diving into Lattice based crypto, LWE and ring LWE. I realise that the hard problem involving them is the "shortest vector problem"...
3
votes
2answers
217 views

Ring-LWE in other fields

Can someone please tell me why in R-LWE we always make use of Cyclotomic fields, and specially those with degree equals to a power of $2$? Can we use another fields without losing in hardness of the ...