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
3
votes
2answers
421 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
51 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"...
1
vote
0answers
47 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 ...
3
votes
2answers
88 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
34 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
23 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?
2
votes
2answers
63 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 ...
4
votes
0answers
292 views

ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc

While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
4
votes
2answers
163 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. ...
0
votes
0answers
58 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
65 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
51 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 (...
0
votes
1answer
92 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
127 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 ...
1
vote
0answers
41 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
36 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,
3
votes
1answer
84 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
74 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 ...
2
votes
1answer
138 views

Threshold decryption in multi-key homomorphic encryption

I have a problem understanding the security of threshold decryption in multi-key homomorphic encryption (MKHE) with so called "noise flooding". In particular I think that it is not secure, so probably ...
1
vote
1answer
149 views

Fully Homomorphic Encryption - state of the art

What are the latest advances in fully homomorphic encryption? First of all, I am interested in cryptosystems based on LWE / RLWE and NTRU problems.
2
votes
1answer
42 views

Security of somewhat homomorphic encryption via LSB encoding?

I'm reading this paper https://eprint.iacr.org/2011/344.pdf It says that "The secret-key encryption scheme whose security is based on the LWE assumption is rather straightforward. To encrypt a bit, $...
3
votes
1answer
86 views

Is there an adaptive version of LWE assumption with respect to some potentially non-uniform secret distribution?

There is a version of LWE assumption as follow. Assume that there is a positive number $n$, an integer $q = q(n) \geq 2$, an error distribution $\chi = \chi_{n}$, a vector $\mathrm{\mathbf{s}} \gets \...
1
vote
0answers
40 views

Solving for secret s in LWE problem

in LWE instance $b=A^t s +e$, can we find an orthogonal basis of coefficient matrix A in polynomial time, let it be B.Multiply B to get $Bb=Be$ as term with s will vanish. Then solve for $e$. After ...
6
votes
1answer
100 views

Is LPN not as important as LWE and SVP?

I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, ...
2
votes
0answers
54 views

ZKPoK for RLWE secret and error

I came across How to validate the secret of a Ring Learning with Errors (RLWE) key paper by Ding et al., which seems to provide a ZK proof that the given $p$ is of the form $as + e$ with $s, e$ small ...
3
votes
0answers
40 views

Choosing the Bernoulli distribution for LPN encryption scheme

The symmetric-key encryption scheme from [1] is based on the LPN (learning parity with noise) problem. The definition of the problem is, informally, that the adversary cannot recover $\mathbf{s}$ from ...
3
votes
1answer
102 views

LWE secure with one entry without noise

I'd like to know, is Learning With Error (LWE) (with modular noise) "secure" if one entry has no noise? More precisely, I have: a random matrix $A \in \mathbb{Z}_q^{m \times n}$ a random string $s \...
2
votes
0answers
45 views

Why round off vector sampling from continuous Gaussian distribution not directly sample from discrete Gaussian distribution

For any vector $\mathbf{c}$, real $s > 0$, and lattice $\Lambda$, define the probability distribution $D_{\Lambda, s,\mathbf{c}}$ over $\Lambda$ by $$D_{\Lambda, s,\mathbf{c}}(\mathbf{x})=\frac{...
4
votes
1answer
261 views

Why does Learning With Errors require a bunch of samples?

Solving Learning with Errors(LWE) with average case complexity is as hard as solving the SVP with worst case complexity. LWE requires $n$ dimensional lattice and $m$ samples of it, and Decisional-LWE ...
1
vote
0answers
125 views

How to solve a simple case of a RLWE problem

I've been reading up on the Ring Learning with Errors problem and the proposed attacks, in relation to homomorphic encryption. Some of the literature has been quite difficult to understand - what I ...
4
votes
0answers
32 views

How can I geometrically understand LWE ciphertext and decryption step?

In the bottom of the wikipedia article of LWE (https://en.wikipedia.org/wiki/Learning_with_errors), we can see construction of Public-key cryptosystem based on the LWE. But, I cannot understand whole ...
8
votes
1answer
182 views

Number of LWE samples in NewHope

This is regarding the number post-quantum key exchange protocol New-Hope (https://eprint.iacr.org/2015/1092.pdf). In the paper, we can see that the number of samples generated by the protocol is $2n$ ...
1
vote
1answer
140 views

What is the purpose of adding secondary error to calculated key in BCNS and NewHope protocols

The answer to this question might be trivial or very short, but I would like to ask it anyway. In both BCNS and NewHope Ring-LWE key-exchange protocol one party adds a secondary error to their ...
1
vote
0answers
59 views

How does the polynomial module impact the security of ring/lattices-based SIS problem?

Consider the following SIS problem: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $(R_q)^{r \times n}$=$\left(\mathbb{Z}_q[X]/(X^N+1)\right)^{r \times n}$ and $q$ a ...
1
vote
0answers
53 views

Probability of an RLWE sample

Let $R_q=\mathbb{Z}_q[x]/(x^n+1)$ as usual in the RLWE assumption. Suppoes that I choose a sample of the RLWE distribution, that is, I compute $(a,y=as+e)$ where $a$ is uniform in $R_q$ and $s,e\...
4
votes
2answers
131 views

Hardness of LPN problem with small secret

The Learning Parity with Noise (LPN) assumption states that, for a fixed secret $s$ chosen uniformly from $\{0,1\}^n$, then the distribution that outputs $(a,a\cdot s+e)$, where $a$ is uniform in $\{0,...
0
votes
1answer
127 views

Refreshing Procedure in FHEW: membership test

I am facing an issue regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second. It concerns the MSBextract algorithm during the refresh procedure. Especially, they ...
6
votes
0answers
161 views

Does there exist trapdoor permutation from lattices?

It seems that the lattice functions are either surjective (SIS) or injective (LWE), due to the error that is basically intended to destroy the structure and provide security. I was wondering whether ...
4
votes
1answer
173 views

Adapting LWE Trapdoors for Ring-LWE

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE. Theorem 5.1: There is an ...
7
votes
1answer
373 views

Are LPN and LWE problems equivalent?

Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits. But, this also makes LPN seem very related to the problem ...
4
votes
1answer
166 views

Minimum distance between polynomials in ring-LWE

Let $R_q=\mathbb{Z}_q[x]/\langle f(x)\rangle$ where $f(x)=x^n+1$, as in the ring-LWE problem. Let $a(x)$ be chosen uniformly at random from $R_q$. Question: Is there any theorem that lower bounds ...
5
votes
0answers
1k views

How to explain Learning With Errors? [closed]

I am trying to understand this concept of Learning With Errors. There does not seem to be a layman explanation of it anywhere. Here I describe layman as someone who understands ML concepts a bit (non ...
1
vote
0answers
44 views

Gate count for Ring-LWE

In one of my recent research, I need to compare the number of gates needed in Ring-LWE encryption to AES in the circuit model. For AES we can find some estimation like this site, but for Ring-LWE we ...
2
votes
1answer
120 views

Probability distribution function in Regev Cryptosystem

In Regev - On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, chapter 5, Public Key Crypto System, it is stated that The probability distribution function $\chi$ is taken to ...
3
votes
1answer
148 views

Encoding of the message in Regev encryption

In public key encryption from LWE, we do the following steps $\textbf{PKE.KeyGen($1^n$)}$ takes as input the security parameter n, samples $A \leftarrow \mathbb{Z}_p^{n \times m}$ and $\textbf{e} \...
2
votes
1answer
131 views

A query on Learning with errors(LWE) problem

In generating an LWE sample, we do $s\xleftarrow{$}\mathbb{Z}_q^{n}, A \xleftarrow{$}\mathbb{Z}_q^{n \times m}~$and $e\xleftarrow{$}\mathbb{{\chi}^{m}}$ Then we compute $b^T$ = $s^TA$ + $e^T$ and ...
4
votes
1answer
200 views

Decision-LWE to Search-LWE

Regev requires $q$ to be prime on lemma 4.2 of his paper for LWE. Why does he require that and how this effect the proof of lemma 4.2?
7
votes
1answer
407 views

A RLWE promise problem

Let $(R , \chi$) be a standard RLWE problem instance. I.e. $R$ is a finite degree polynomial ring over a finite field and $\chi$ is some gaussian distribution over R with small variance. I wonder ...
1
vote
0answers
42 views

What are general circuits exactly?

This may be a silly question but while reading this paper Circuit ABE from LWE, I came across this question on 2nd page - Is there an ABE scheme for general circuits with unbounded attribute length ...
0
votes
1answer
133 views

LWE with secret matrix (Reverse LWE?)

I was wondering if there is a version of LWE with secret matrices and public seed vectors? Would it be as hard as the popular definition of LWE?