Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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).

1
vote
0answers
27 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
35 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\...
1
vote
1answer
40 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 \...
4
votes
2answers
84 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
76 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 ...
5
votes
0answers
80 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 ...
6
votes
1answer
94 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
123 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 ...
1
vote
0answers
39 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 ...
3
votes
1answer
102 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 ...
2
votes
1answer
88 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
86 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
107 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
0answers
542 views

How to explain Learning With Errors?

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 ...
4
votes
1answer
113 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?
1
vote
0answers
39 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
77 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?
1
vote
1answer
131 views

Is it secure using LWE-based cryptosystem under RLWE-based parameters?

I'm computer guy having trouble with cryptography. I recently read the BGV Homomorphic encryption paper which was constructed under both LWE and RLWE assumptions. I was implementing Threshold ...
2
votes
0answers
55 views

Does secure LWE implementation leak bit information?

We know RSA leaks one bit about the factors and improper yet secure implementations of Discrete Logarithm leak one bit about the discrete logarithm. Does LWE leak any information?
2
votes
1answer
93 views

Interpreting Figure 1 in the “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography”

I'm reading "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography" by O. Regev. I'm having trouble with understanding graphs in Figure 1. By the definition of $\overline{\psi}_{\...
3
votes
1answer
79 views

Why don't we use an Extendable Output Function to efficiently store the public key of Regev's LWE-based encryption scheme over standard lattices?

In LWE-based schemes the public key is generated by choosing a random matrix (or polynomial) $A$, and outputting the pair $(A, b = A\cdot s + e)$, where $s$ and $e$ are vectors/polynomials with ...
2
votes
0answers
86 views

Distinguishing advantage in terms of $\Omega(\omega)$

I was going through this paper ("Fully Homomophic Encryption over the Integers Revisited") and the statement written in the first paragraph on page 5 stating $\DeclareMathOperator{\agcd}{AGCD}$ We ...
3
votes
0answers
189 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, ...
0
votes
1answer
64 views

Gaussian elimination to equations with errors

I am reading this document and wondering the following part on page 13: "Consider applying Gaussian elimination to the noisy samples to find the first bit" If we take, for example, $n = 3$, $s = (...
7
votes
2answers
349 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 ...
3
votes
1answer
131 views

R-LWE instantiation with non-power of 2 polynomial

In almost all RLWE papers, the polynomials are chosen from a ring $\mathbb{Z}[x]/f(x)$ where $f(x)$ is a polynomial of the form $f(x)=x^{2^n}+1$. That leaves us the choice of polynomials like $x^{256}+...
2
votes
0answers
55 views

show how LWE errors can have a greater impact on result

Hi weve been given the following question in one of our classes but have not been taught anything about it and is worded strangely. It is to show how the LWE problem works by showing how small errors ...
1
vote
0answers
36 views

Effect of small secret attacks on non homomorphic encryption schemes

The new paper by Albrecht describes a new attack on "unusually" small secrets that are used in homomorphic encryption schemes. In the paper the talk about binary secrets or LWE Normal form i.e $\...
1
vote
0answers
35 views

Batching in LWE based Crypto-System

Is batching possible for a LWE based crypto-system like we do for a RLWE based one?
2
votes
0answers
132 views

Security analysis of LWE with unequal error and secret distribution

Analysis of security of recent LWE based Key-exchange schemes, the error and secret vector is always chosen from the same Gaussian distribution. What will be the impact on the security if $\sigma_s\...
3
votes
1answer
176 views

Pseudorandomness of ring learning with errors

My question is in Ring Learning with Errors, let $a(x)\in \mathbb{Z}_q(x)/(X^n+1)$ where $n$ is a power of $2$, be a random polynomial, $s(x),e(x)\in \mathbb{Z}_q(x)/(X^n+1)$ are the secret and error ...
3
votes
1answer
211 views

CCA2-secure encryption based on LWE/Ring-LWE

As I understand it, cryptosystems based on LWE/Ring-LWE are typically only IND-CPA, and fail to satisfy IND-CCA2. In fact, it appears that chosen ciphertext attacks could allow secret key recovery (!)...
2
votes
1answer
160 views

A Simple Provably Secure Key Exchange Scheme Based on the LWE

In this paper (A simple provably secure key exchange by Ding et al.), I am trying to understand the correctness (which is given on page number 8) of the key exchange technique based on LWE. To ...
3
votes
1answer
149 views

Security estimation of LWE using “On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL”

I recently found this paper eprint which estimates security of LWE instantiations using an improved Dual attack. However, I got confused looking at their example in this site. For example, in the case ...
5
votes
1answer
269 views

How the condition $s \geq 8$ is determined in Lindner-Peikert cryptosystem?

In Lindner & Peikert paper, the authors propose that to set the cryptosystem's parameters, one should choose $q$ to be large enough to allow for a Gaussian parameter $s \geq 8$. My question is, ...
5
votes
3answers
260 views

A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem

In this paper (A simple provably secure key exchange by Ding et al.) At page number 8, the author gives correctness of the technique as follows then SK A = SKB with overwhelming probability i.e. if ...
1
vote
0answers
128 views

How to provide security against malicious adversary in Ring LWE homomorphic encryption scheme?

I was reading Ring LWE homomorphic encryption scheme referred in http://www.wisdom.weizmann.ac.il/~zvikab/localpapers/IdealHom.pdf But this encryption scheme provides security mostly in the semi-...
8
votes
2answers
670 views

Why is Ring-LWE more efficient compared to LWE?

Can someone please tell me why is the Ring-LWE more efficient? By introducing polynomials in place of matrices, what kind of optimizations do we introduce that make Ring-LWE more efficient?
8
votes
1answer
182 views

LWE: error and float operations

Background I'm trying to make sense of the error in implementations of LWE and R-LWE. In LWE and R-LWE error is added to vectors in lattices to make it computationally infeasible to recover any ...
3
votes
0answers
83 views

LWE status versus modern deployed crypto [closed]

LWE is the one of the most promising post quantum strategy. How does parameters (key sizes, time for encryption etc) for LWE compare with modern deployed standards such as Factoring or discrete log ...
8
votes
1answer
153 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$ ...
7
votes
2answers
251 views

Understand LWE(Learning With Error) negligible error probability

According to Regev's paper, p15 Correctness. Note that if not for the error in the LWE samples, $b-⟨a, s⟩$ would be either 0 or ⌊ q ⌋ depending on the encrypted bit, and decryption would always be ...
1
vote
1answer
187 views

Why in BCNS protocol both parties don't follow the exact same key extraction approach

Why in BCNC key-exchange protocol (page 8), Bob instead of: $K_B \leftarrow \lfloor \bar v \rceil_{2q,2} \in \{ 0, 1\}^n$ do this instead: $K_B \leftarrow rec(2bs', c) \in \{0, 1\}^n$. or they are ...
0
votes
0answers
135 views

Security of Lindner-Peikert parameters for lwe

From Regev's paper in 2005, we know that for applying worst-case to average-case reduction to an lwe cryptosystem, one should use error distributions with standard deviation $s$ bigger than $2\sqrt{n}$...
1
vote
1answer
103 views

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

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 calculated ...
3
votes
1answer
599 views

Parameters for LWE

In the LWE problem there are two methods in order to choose secure parameters. The Lindner-Peikert and Micciancio-Regev method. The first method is an attack to BDD : find closest vector knowing the ...