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

161 questions
Filter by
Sorted by
Tagged with
16 views

### Cryptographic functions as feature map/kernel function?

Has there been any use of cryptographic function as a kernel function with support vector machine? There are several standard kernels to be used with SVMs each with its own scenario. I was not able to ...
• 151
38 views

### Regev PKE not CPA secure for specific $A$?

I encountered notes stating that, for certain fixed $A$, such as $A \in M_{n\log(q)\times n}$ as follows: \begin{bmatrix} 1 & 0 & 0 &\dots\\ 2 & 0 & 0 &\dots\\ 4 & 0 & ...
• 311
72 views

### Statistical Distance and Learning with Rounding

Given an integer $b$ modulo a prime $q$, one can define a `rounding’ function $\lfloor b\rceil_p$ for a prime $p$, $p<q$, as follows: $$\lfloor b\rceil_p = \lfloor \frac{p}{q}\cdot b\rceil\bmod p.$$...
• 381
1 vote
48 views

### Type 1 Trapdoor Sampling in LWE

In the BGN-like LWE cryptosystem, section $2.2$, we sample a $m \times m$ trapdoor matrix $T$ that is full rank such that $TA = 0 \pmod q$. Suppose that $q$ is prime so we are in a finite field: if $T$...
128 views

### Finding the exact solution of an LWE instance with a sparse matrix

I already asked a question about the feasibility of LWE when the matrix A is sparse or small here. Let $q$ be a prime, let $\chi$ be a distribution of $\textit{small}$ elements over $\mathbb{Z}/q$, ...
• 113
1 vote
61 views

### LPN over non-binary fields

With regard to LPN over non-binary fields like $\mathbb{F}_3,\mathbb{F}_5,\cdots$, are there any studies about that ? We also would like to know any articles that have a formal definition of the non-...
• 11
24 views

### SIMD mode for RGSW encryption?

I know schemes like BFV, BGV, and CKKS supports SIMD operations where the plaintext is vector of values instead of polynomial. I am wondering if RGSW/TFHE kind of schemes can also support SIMD ...
• 239
44 views

### How to hide result of FHE?

Lets say we are given BFV encryption of x, let this encryption is represented as E(x). In FHE, the client can decrypt and get ...
• 239
1 vote
108 views

• 337
94 views

### LWE-search to SVP reduction

So for my diploma thesis I'm writing about Regev's LWE cryptosystem from his original 2005 paper. I'm done with with correctness and security (only reduction from LWE-search via average-to-worst and ...
• 11
107 views

### LWE with the matrix A repeated

Consider the following version of Learning With Errors. You are either given $(A, As_1 + e_1, As_2 + e_2, \ldots, As_k + e_k)$ or $(A, u_1, u_2, \ldots, u_k)$, where $A$ is an $m \times n$ matrix ...
• 337
1 vote
121 views

### Why RLWE is lighter than LWE and why we can pick $a_i$ as a permutation of $a_1$ in RLWE but not LWE?

In LWE, we have $$<a_1,s> + e + \mu_1\in \mathbb{Z}_q$$ for a secret key $s\in \{0,1\}^n$ and $a_1\in \mathbb{Z}_q^n$ This is an encryption of a number $\mu_1$. If we want to encrypt $n$ ...
1 vote
65 views

### How to prove reduction from decision to seach LWE?

I am new to cryptography, and trying to understand the concepts of LWE (learning with errors) formally. I will state my understanding of the definitions, which might be incorrect. Definitions ...
• 145
1 vote
95 views

• 337
20 views

### Number of samples in FrodoKEM

Why does the number of samples in FrodoKEM is $m \approx n$? The paper is here.
• 365
54 views

### A smaller modulus-to-noise ratio means more security in LWE

Let $\text{Adv}^{\text{DLWE}}_{n,m,q,\sigma}$ be the advantage of an attacker to distinguish LWE samples from uniform ones, where $m$ is the number of samples, $q$ the modulus and $\sigma$ the ...
• 365
112 views

### LWE and extended trapdoor claw free functions

Let $q \geq 2$ be a prime integer. Consider two functions, given by: $$f(b, x) = Ax + b \cdot u + e~~~(\text{mod}~q),$$ $$g(b, x) = Ax + b \cdot (As + e') + e~~~(\text{mod}~q),$$ where we have: \begin{...
• 337
In an algebraic number field, an ideal $I$ in the ring of integers $\mathcal{O}_K$ has dual $I^\vee = \{x\in\mathcal{O}_K\text{ : }T_{K/\mathbb{Q}}(xy)\in\mathbb{Z}\text{ for all }y\in I\}$, where $T_{... • 381 2 votes 1 answer 79 views ### How is it legal to use a rounded Gaussian for LWE? As far as I understood, in Regev's initial paper, the error distribution was first constructed as follows: Then rounded in the following way: Using this distribution, the reduction in the theorem ... • 365 1 vote 0 answers 46 views ### polynomial time reduction from SIS to decisional-LWE? Is the claim "If there is an efficient algorithm that solves SIS, then there is an efficient algorithm that solves decisional LWE" is sufficient? or, Is the claim above is equivalent to the ... • 11 2 votes 1 answer 91 views ### LWE and pseudorandom functions Consider the learning with errors problem. Assuming LWE (or a variant of LWE, like ring LWE) is hard for polynomial time algorithms, can we construct a family of pseudorandom functions from there? • 337 2 votes 2 answers 106 views ### LWE - Encrypting/Decrypting messages bigger than 1 bit I'd like to know if LWE (and its variants: RLWE and MLWE) can cipher messages bigger than 1 bit. Is it possible? I didn't find any reference yet. Could you explain it to me or give some good ... 1 vote 0 answers 78 views ### The relationship between root hermite factor and bit-security? The root hermite factor corresponding to an bit-security level, such as 1.0045 corresponding to 128-bit security. What is the root hermite factor corresponding to 100-bit, 160-bit, 180-bit security? ... 0 votes 0 answers 26 views ### How to estimate the parameter of a lattice signature scheme with lossy reduction? The parameter of a lattice signature scheme DAZ19 with tight reduction can be choosed to make the underlying hardness problem intractable. How to estimate the parameter of a lattice signature scheme ... 3 votes 0 answers 48 views ### parameter estimating in lattice signature scheme when reading [BDLOP18], I run the lwe-estimator with the recommended parameters in Table 2 , but the result of hermite factor is 1.007, this result is bigger than the recommended hermite factor 1.0035 2 votes 2 answers 92 views ### *-LWE equivalent of Diffie-Hellman$g^{x^2}$vulnerability In Is Diffie-Hellman less secure when A and B select the same random number? , the possibility of Diffie-Hellman key exchange producing identical peer keys and the vulnerability of it against passive ... • 7,103 3 votes 0 answers 72 views ### Is the scheme in LWE also valid in R-LWE? One way of interpreting matrices in RLWE is that they are a subset of standard integer matrices that have special structure. For example, rather than using a random matrix$A\in\mathbb{Z}_q^{n\times n}...
Are there any constraints when it comes to proving that search-LWE and decision-LWE are equivalent? Should we assume that the module $q$ is prime when switching from one version to another? Please ...