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).
65
questions
0
votes
0answers
31 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
33 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
67 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 ...
5
votes
0answers
90 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
76 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
59 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
1answer
98 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.
...
2
votes
1answer
70 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
94 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
39 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, $...
1
vote
0answers
37 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 ...
3
votes
1answer
79 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 \...
5
votes
1answer
79 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
49 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 ...
2
votes
0answers
34 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 ...
2
votes
0answers
38 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{...
1
vote
0answers
83 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 ...
3
votes
0answers
31 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 ...
1
vote
0answers
57 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
49 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\...
3
votes
1answer
88 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
111 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
126 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
138 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 ...
7
votes
1answer
235 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
152 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
43 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
146 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
116 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
129 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
129 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
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 ...
4
votes
1answer
161 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
41 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
109 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
156 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
58 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
96 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
89 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
96 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
243 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
69 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 = (...
4
votes
1answer
247 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 ...
7
votes
1answer
401 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
150 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
37 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
40 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
146 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
203 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 ...
