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).
107
questions
2
votes
1answer
26 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
35 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
43 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
59 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
58 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
34 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
52 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
49 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
59 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
46 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
27 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
43 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
265 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
21 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
209 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
120 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
68 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 $\...
1
vote
1answer
67 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
55 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
27 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
37 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
105 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
39 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
66 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
134 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
80 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
80 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
57 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
38 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
438 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
64 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
242 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
39 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
468 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
105 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
176 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 ...
0
votes
0answers
42 views
Binomial distribution sampling - concrete example
Can anyone give me an explicit example of how one can samples from the binomial distribution defined in NewHope's paper? What is the difference of sampling from rounded Gaussian in practice?
1
vote
0answers
31 views
Difference between polynomial embedding and canonical embedding
Can anyone tell me the difference between working in the polynomial embedding for $R$-LWE, and working in the canonical embedding?
1
vote
0answers
50 views
Proof for, Vectors sampled from $D_{(L,r)}$ have Euclidean norm at most $r\sqrt{n}$ with a high probability
For any $n$-dimensional lattice $L$ and $r > 0$, a point sampled from $D_{L,r}$ has Euclidean norm at most $r\sqrt{n}$ except with probability at most $2^{-2n}$ (where $r$ refers to the standard ...
2
votes
2answers
79 views
LWE versus neural nets
It seems like that the construction of the LWE problem: $As + e = b$ resembles how neural nets work: $Ax + b = y$.
In LWE, we are given the problem instance $A$, and the product with errors $b$ and ...
0
votes
0answers
66 views
Hash chain based secret revealing using homorphic princples?
I have recently been looking into Homomorphic encryption and I am looking for a specific hash-based encryption/decryption scheme.
I don't need a full implementation but I am not sure if what I want ...
3
votes
1answer
95 views
Hardware Gaussian random numbers for lattice-based cryptography
I have been recently reading about lattice-based cryptography.
I read that a key aspect of such protocols rely on added Gaussian noise on lattices, and which therefore require highly efficient and ...
4
votes
1answer
63 views
Is Type I lattice trapdoor hard to find even given oracle access to compute inverse of trapdoor function?
Consider the Type I lattice trapdoor in [GPV08]: https://eprint.iacr.org/2007/432.pdf
Suppose a PPT adversary is given the LWE trapdoor function in the picture:
$g_{A^\top} (s,e) = A^\top s + e = b (...
1
vote
0answers
56 views
Multibit LWE Encryption
What's the simplest way to encrypt multiple bits with LWE public key cryptosystem? Some paper say use a different secret key for each bit of the message. Does that mean the length of the message ...
0
votes
1answer
45 views
learning with errors is hard even when given some information about the secret vector
In this case we are given the distribution D from which secret s is sampled. If I can get some hints to proceed with the questions, it would be of help.
Thanks,
0
votes
1answer
110 views
Trying to Understand Ring Learning With Error Encryption
I'm trying to understand the following RLWE encryption scheme from this Chris Peikert's paper
Say i choose $q = 97$, $n=8$ and the polynomial
$a = 96 x^8+30 x^7+76 x^6+12 x^5+57 x^4+77 x^3+70 x^2+49 ...
6
votes
1answer
191 views
Decision to Search LWE when modulus $q=p^e$
I am reading Applebaum et al..
In Lemma 1. (page 7), Applebaum et al. proved the decision to search reduction when the modulus $q=p^e$ for prime $p$.
In the proof, they define the hybrid ...
3
votes
1answer
89 views
Randomness of Decision Learning With Error Problem
I read the statement of the Decision Learning with error problem is:
distinguish between $(\vec a, \langle \vec a, \vec s \rangle + e)$ from uniformly random samples.
Can anyone explain what does ...
0
votes
1answer
89 views
understanding LWE public key algorithm
I'm trying to understand this LWE public key system
say I use matrix A = [[44, 73, 20, 54],[92, 19, 78, 22],[31, 34, 94, 29],[82, 32, 70, 68]]
q = 97
bit = 1
and secret key s: [56, 90, 0, 46]
and ...
4
votes
2answers
239 views
what does output parameters of lwe estimator stands for?
I want to use lwe estimator to find classical and quantum security of my proposed key exchange protocol. On this website, I want to understand the output of sage code on lwe estimator given bellow.
...
