Skip to main content
31 votes

What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?

There is no public paper available yet, so this answer is preliminary and based on what was presented in the talk and the follow-up discussion. A full understanding cannot be reached until there is a ...
Chris Peikert's user avatar
30 votes

Kyber and Dilithium explained to primary school students?

I'll take that challenge for Kyber, but I fear that a simplification of Dilithium could more easily lead to a dangerous understanding. I'm going to describe a cryptographic design, mini-Kyber, that is ...
Daniel S's user avatar
  • 24.1k
26 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
22 votes

Why are only lattice problems used in cryptography?

What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard. What is required for cryptography is average-case hardness --- i.e., a randomly selected ...
ckamath's user avatar
  • 5,338
21 votes
Accepted

Is lattice-based cryptography practical?

Yes, it is feasible. In fact, the NIST post-quantum submissions include a number of lattice-based cryptographic key exchange and signature protocols. As you can see from a summary of the different ...
forest's user avatar
  • 15.3k
20 votes
Accepted

New quantum attack on lattices (or Shor strikes again)?

As mentioned in the comments, there is a serious flaw in the paper, and it has been withdrawn: see https://groups.google.com/forum/#!msg/cryptanalytic-algorithms/WNMuTfJuSRc/OtQMLRXgBwAJ and part (3) ...
Chris Peikert's user avatar
16 votes

New quantum attack on lattices (or Shor strikes again)?

The authors themselves point out that this doesn't break lattice-based assumptions used in crypto. To quote: Lattice problems have received enormous attention in recent years, mainly because of ...
Yehuda Lindell's user avatar
15 votes

Uniform vs discrete Gaussian sampling in Ring learning with errors

The TL;DR: From a theoretic point of view, Gaussians are the better choice, both for the easiness of the security proof and its optimality in terms of tightness; In practice, most of the time you can ...
Thomas Prest's user avatar
  • 1,080
15 votes

New quantum attack on lattices (or Shor strikes again)?

Unless I misunderstood the definitions, an algorithm for the problem in Definition 1 (i.e. their main result) is in fact enough to attack decision-LWE if the noise is small. The fact that they need a ...
Vadim L.'s user avatar
  • 1,146
15 votes
Accepted

Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?

The first inequality at the bottom of page 3 of the paper is false. For example, Conway and Thompson proved the existence of "self-dual" $n$-dimensional lattices $L$ (i.e., $L^* = L$) where $\lambda_1(...
Chris Peikert's user avatar
14 votes

Is lattice encryption susceptible to Grover's algorithm?

The best attack on the exact shortest vector problem for an arbitrary lattice (to which essentially all lattice reduction attacks on lattice-based schemes reduce in some way) is some variant of ...
Mehdi Tibouchi's user avatar
14 votes
Accepted

Impact of Ryan and Heninger's CRYPTO 2023 paper on post quantum cryptosystems

The following is mostly known to lattices people (and mentioned at the end of the Quanta article), but I also reached out to Keegan to clarify some questions I had. There are (roughly) two main types ...
Mark Schultz-Wu's user avatar
  • 13.5k
13 votes

Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?

Independently of the algorithmic claim, I indeed have serious doubts about Theorem 2. Here is a counterargument (using standard techniques) cooked up with Yang Yu and Wessel van Woerden: Suppose ...
LeoDucas's user avatar
  • 1,253
13 votes

Current Consensus on Security of Lattice Based Cryptography?

The claimed attack does not "break" lattice-based cryptography, merely further improves known attacks. I'll try to briefly describe the situation. Asymptotics: Asymptotically, our best ...
Mark Schultz-Wu's user avatar
  • 13.5k
13 votes

Kyber and Dilithium explained to primary school students?

Despite Daniel's valiant effort I think the correct answer is no, you can not with reasonable effort explain the inner workings of post quantum cryptography to most primary school students. You should ...
Meir Maor's user avatar
  • 11.8k
12 votes
Accepted

Converting NewHope/LWE key exchange to a Diffe-Hellman-like algorithm

It has been folklore (since at least 2010) that you can do what you propose, but less efficiently than the "key transport" method of any Ring-LWE based encryption scheme or KEM. So here is what you ...
Vadim L.'s user avatar
  • 1,146
12 votes

Why is lattice-based cryptography believed to be hard against quantum computer?

I'm unaware of a great answer to this problem. There are "partial answers", but they are not great. Still, they are what I use to (vaguely) explain things, being someone interested in ...
Mark Schultz-Wu's user avatar
  • 13.5k
12 votes
Accepted

Discrete Gaussian Sampling role in Lattice-Based Crypto?

A Gaussian distribution satisfies the following desirable properties: It can be implemented coordinate-wise: If $x_1, x_2, \ldots , x_n$ are each sampled from a one-variable Gaussian distribution, ...
djao's user avatar
  • 776
11 votes
Accepted

Why is the Lovász condition used in the LLL algorithm?

The issue with the length-reduction criterion alone (and the reason the Lovász condition is included in the LLL algorithm) is that the following basis satisfies it: (The grey arrow is the projection ...
yyyyyyy's user avatar
  • 12.1k
11 votes
Accepted

Why is lattice-based cryptography believed to be hard against quantum computer?

Why is lattice-based cryptography believed to be hard against quantum computer? Because no one has developed a quantum algorithm (yet) that breaks these crypto primitives. Wish we could do better ...
mikeazo's user avatar
  • 38.7k
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
  • 49k
11 votes
Accepted

Why do Problems for Post-Quantum algorithms have to be NP-Hard?

I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why ...
Mark Schultz-Wu's user avatar
  • 13.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
  • 880
10 votes
Accepted

Peikert's framework for attacks on R-LWE: What "reduction modulo q" means?

Recall that any ideal $I$ of $R$ is in particular an additive subgroup of $R$, and that the quotient $R/I$ is the collection of cosets $a + I = \{a + i : i \in I\}$ for each $a \in R$. Two cosets $a+...
Chris Peikert's user avatar
10 votes
Accepted

Relation between decisional SIS and leftover hash lemma in lattices

The leftover hash lemma (LHL) says that $(A,u=Ax) \in \mathbb{Z}_q^{(n+1) \times (m+1)}$ is very close to uniformly random. In particular, this implies that for uniformly random $(A,u)$, there exists ...
Chris Peikert's user avatar
10 votes

What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?

I created a website to crowdsource what is known about algorithms for lattice problems in NP intersect CoNP: https://latticealgorithms.xyz Our paper is up: https://arxiv.org/abs/2201.13450 For the ...
SeanH's user avatar
  • 101
10 votes

Why did NIST select Kyber and Dilithium?

NIST did consider the MATZOV attacks. If we read their Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, we see in section 4.1.1 on page 29: During the ...
Daniel S's user avatar
  • 24.1k
9 votes
Accepted

Irreducible polynomial in Ring-LWE

The cited paper, as well as the theorem of R-LWE in that paper only requires $f$ to be irreducible over the rationals. For this requirement one usually uses $f = x^n+1$ with $n$ a power of $2$. This ...
zhenfei zhang's user avatar
9 votes
Accepted

Why does lattice KEX not require sampling with high precision?

The way and the purpose in which gaussians are used in key exchange and digital signatures is completely different. In public key encryption (and key exchange), we need computational-...
Vadim L.'s user avatar
  • 1,146

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