25 votes
Accepted

Polynomial-time Quantum Algorithms for Lattice Problems

Current status regarding the correctness TL;DR: the attack is not working. Update: Since April 18 a bug has been found in the paper and the author retracted their claim: Further details are listed ...
Léo Colisson's user avatar
11 votes
Accepted

Number of LWE samples in NewHope

They're actually sampling $5n$ elements from $\Psi_{16}$. Perhaps Protocol 2 on page 5 shows this most clearly, where $\textbf{s}, \textbf{e} \stackrel{\$}{\leftarrow} \Psi_{16}^n$ and $\textbf{s}', \...
Joost's user avatar
  • 226
11 votes

NewHope and NIST's Post-quantum standardization

From Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process 3.12 NewHope NewHope is a KEM based on the presumed hardness of the RLWE problem. At its core is ...
kelalaka's user avatar
  • 48.5k
11 votes

Polynomial-time Quantum Algorithms for Lattice Problems

Probably it will take some time for the experts in this community to carefully review the paper to see whether it works or not, since it is quite long and technical. Meanwhile, I feel members of this ...
Wenzhe's user avatar
  • 227
11 votes

Polynomial-time Quantum Algorithms for Lattice Problems

A new paper on ePrint (A Note on Quantum Algorithms for Lattice Problems) claims to have found an error on that paper. Quoting: "Our observation is very simple and can be summed up as that the ...
swineone's user avatar
  • 808
9 votes
Accepted

Are LPN and LWE problems equivalent?

Yes, LPN is (essentially by definition) equivalent to the hardness of decoding a random linear code over $\mathbb{F}_2$. No, there is no known reductions between LPN and LWE. It is usually believed ...
Geoffroy Couteau's user avatar
8 votes
Accepted

Why is Ring-LWE more efficient compared to LWE?

The previous (galvatron's) answer gave two good reasons why Ring-LWE is more efficient. They explain why the running time of LWE schemes is worse than of Ring-LWE ones. (The n^2 vs n equations is ...
Vadim L.'s user avatar
  • 1,146
8 votes
Accepted

LWE and pseudorandom functions

You can. There is a certain caveat that should be mentioned here --- the LWE problems hardness is controlled (in part) by the size of the modulus $q$. Two important parameter regimes are $q$ being ...
Mark Schultz-Wu's user avatar
8 votes
Accepted

RLWE Explanation

The cyclotomic polynomials are used in the proofs that worst-case lattice problems reduce to the RLWE. If you try to instantiate RLWE with other polynomials, then you don't have such formal guarantees ...
Hilder Vitor Lima Pereira's user avatar
8 votes

Polynomial-time Quantum Algorithms for Lattice Problems

Yilei Chen published an update on his website yesterday saying that "Step 9 of the algorithm contains a bug", and that he does not yet know if it will be possible to fix it. TLDR: As of ...
ProfCornDog's user avatar
7 votes
Accepted

Pseudorandomness of ring learning with errors

Let $R$ be the ring $\mathbb{Z}_p[X]/(X^n+1)$, where $n$ is a power of 2. The Ring-LWE assumption says that for any randomly chosen, fixed $s\in R$, the distribution of $$((a_1,a_1s+e_1),\ldots,(a_k,...
Vadim L.'s user avatar
  • 1,146
7 votes

Ring-LWE in other fields

We don’t always use power-of-two cyclotomics for RLWE. Many cryptosystems use other cyclotomics, or subfields thereof, or even other fields altogether. For example, many FHE schemes use non-two-power ...
Chris Peikert's user avatar
7 votes

Distribution of the Difference of Uniformly Random Elements

Firstly, why is this true? This is easy to see, if we consider the finite field as a finite group with the addition operation (and ignore the multiplication operation) If we consider the value $X - Y$...
poncho's user avatar
  • 147k
7 votes
Accepted

MLWE (and RLWE) to LWE reductions proof

There is no known reduction from LWE to MLWE (or to RLWE). That is, it could be that both MLWE and RLWE are broken, yet LWE is secure. However, this seems highly unlikely. To support the security of ...
Geoffroy Couteau's user avatar
7 votes

Ring Learning With Errors : why is it called ring and referred it as Ring LWE

So $R = \mathbb{Z}[x]/(x^n+1)$, where $x^n+1$ is an irreducible polynomial and n is a power of 2. So, this structure would not be a ring anymore, it would be a field. So, why is it called ring and ...
Mark Schultz-Wu's user avatar
5 votes
Accepted

Minimum distance between polynomials in ring-LWE

I'm assuming $n$ is a power of $2$ and that $q$ is an odd prime larger than $n$. I'm discarding the trivial case $s_1 = s_2$. If you consider everything $\mod q$, then it is most likely over the ...
LeoDucas's user avatar
  • 1,213
5 votes
Accepted

Parameters for LWE

As mentioned in the comments, there is still a lot of active research being done in the area of algorithms for solving Learning With Errors, as clearly it's an important topic for estimating the ...
TMM's user avatar
  • 343
5 votes
Accepted

Understand LWE(Learning With Error) negligible error probability

Denote by $X$ the random variable which is the sum over all $S$. As mentioned, this is a Gaussian of standard deviation at most $\sqrt{m}r$ with $r = \alpha q$. Hence, by properties of the (sub-)...
Daniel's user avatar
  • 3,952
5 votes

Understand LWE(Learning With Error) negligible error probability

The probability of error is negligible "as a function of $n$", meaning that the probability of error will decrease (quickly) as $n$ grows. Increasing $n$ should solve your issue.
LeoDucas's user avatar
  • 1,213
5 votes
Accepted

Hardness of LPN problem with small secret

There is a simple trick (known in the LWE literature as the Hermite normal form of the problem) that takes an existing LPN problem and transforms it into a problem in which the secret has the same ...
Samuel Neves's user avatar
  • 12.5k
5 votes
Accepted

Distribution of the Difference of Uniformly Random Elements

It's worth mentioning that the conditions needed for $f(X_0, X_1)$ to be uniformly random based off the distributions of $X_0, X_1$ are quite mild usually. In particular what you need is: $X_0$ and $...
Mark Schultz-Wu's user avatar
5 votes

What is the difference between Poly-LWE and Ring-LWE?

One main difference is that in Ring-LWE, the ring $R$ is the full ring of integers $\mathcal{O}_K$ of a number field $K$, whereas in Poly-LWE it is of the form $R=\mathbb{Z}[x]/f(x)$ for some ...
Chris Peikert's user avatar
5 votes
Accepted

CRYSTALS-KYBER versus FrodoKEM, what makes each of them different than the other?

There are a few cosmetic differences but the principal difference is the matrix $A$ in the LWE problem. In Frodo it is consciously unstructured, but in Kyber it has some symmetry. Specifically in both ...
Daniel S's user avatar
  • 23.9k
4 votes

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

This lemma is used to conclude that a sample from $\mathcal{D}_{\mathbb{Z}^n,\alpha q}$ is (with overwhelming probability) less than or equal to $\alpha q \sqrt{n}$. Now, because all values $\textbf{...
Hamidreza's user avatar
  • 1,019
4 votes
Accepted

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?

I believe it is also used in other lattice based schemes that use standard LWE. For example, the Frodo paper. They used a $seed_A$ and a Gen($\cdot$) function to compute $A$. Then Alice sends $seed_A$ ...
zhenfei zhang's user avatar
4 votes
Accepted

Why does Learning With Errors require a bunch of samples?

The number of rows in matrix $\textbf{A}$ shows the number of LWE samples and $m=1$ means the adversary has access only to one sample. This would be a naive adversary model and would not be suitable ...
Hamidreza's user avatar
  • 1,019
4 votes
Accepted

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

I asked the question to the author directly. To answer the first question, authors of NewHope estimate their security very conservatively, whereas the estimator takes many other things into account. ...
Rick's user avatar
  • 1,265

Only top scored, non community-wiki answers of a minimum length are eligible