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

26 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
159 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
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 ...
4
votes
0answers
291 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, ...
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 ...
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 ...
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{...
2
votes
0answers
59 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
0answers
106 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 ...
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 ...
2
votes
0answers
148 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\...
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
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?
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 ...
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 ...
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 ...
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 ...
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\...
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 ...
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 ...
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
42 views

Batching in LWE based Crypto-System

Is batching possible for a LWE based crypto-system like we do for a RLWE based one?
1
vote
0answers
145 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-...
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?
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 ...
0
votes
0answers
156 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}$...