Live data from Hacker News

Quantum Algorithms for Lattice Problems

eprint.iacr.org

11–20 of 127 posts

Re: Quantum Algorithms for Lattice Problems

#11
post #8

How does this affect these statements on Wikipedia [1] > some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently. and [2] ? > One class of quantum resistant cryptographic algorithms is bas…

The idea of "appear to be resistant to attack" is an empirical one. When someone says that, they are saying that we simply have not found a good attack against this problem. That can change any day, in principle. Unfortunately, "we don't know of an attack" is about as strong a statement you can make in cryptography, when talking about a fundamental hardness assumption. More verbosely, you'd say "the best known attacks take 2^whatever operations on a computer (classical or quantum), and that's expensive, so we're probably fine unless someone makes a significant leap tomorrow"

Re: Quantum Algorithms for Lattice Problems

#13
post #8

How does this affect these statements on Wikipedia [1] > some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently. and [2] ? > One class of quantum resistant cryptographic algorithms is bas…

Do you know how little we know? We don't even know P isn't PSPACE!

Re: Quantum Algorithms for Lattice Problems

#14
post #4

If the findings of this paper hold up, I believe it could pretty much undo a decade of NIST's efforts in post-quantum cryptography. a seismic shift in the world of cryptography.

This is the reason why nist did the decade of work - to focus effort on figuring out what options are secure. Finding out an option is not secure is a good thing. Its why we are putting effort into PQC now before quantum computers are a real threat.

Re: Quantum Algorithms for Lattice Problems

#15
post #7

Does this result apply to all LWE problems? Does this approach care about LWE vs Ring-LWE at all? If so, it's a big blow to systems like FrodoKEM that banked on unstructured lattices providing higher security.

Not a lattice expert, so add salt to taste, but it looks like LWE in general (incluring RLWE)

But the current attack essentially wants q > n^2, so even if it is confirmed, not all LWE schemes are dead. There will certainly be people who tweak the params in response and carry on.

However, attacks only get better. And for people in FHE who are squeezed between performance problems and dangerously thin security parameters, it is a bad day if confirmed. There's no credible practical alternative to LWE for FHE...

Re: Quantum Algorithms for Lattice Problems

#16
post #7

Does this result apply to all LWE problems? Does this approach care about LWE vs Ring-LWE at all? If so, it's a big blow to systems like FrodoKEM that banked on unstructured lattices providing higher security.

RingLWE security reduces to LWE via a relatively simple reduction (see https://www.jeremykun.com/2022/12/28/estimating-the-security...).

Re: Quantum Algorithms for Lattice Problems

#18
post #10
post #4

If the findings of this paper hold up, I believe it could pretty much undo a decade of NIST's efforts in post-quantum cryptography. a seismic shift in the world of cryptography.

Not entirely true, there are other PKE and DSA algorithms that were/are a part of the competition that used problems not related to lattices. However, the lattice-based options were often among the fastest and smallest.

Isogenies vindicated? :)

Re: Quantum Algorithms for Lattice Problems

#19
I work on homomorphic encryption, and there are some rumors circulating that, if this checks out, it will break some of the leading FHE schemes like BFV, where the moduli used are quite large (in the hundreds of bits or even over a thousand bits).

Re: Quantum Algorithms for Lattice Problems

#20
post #4

If the findings of this paper hold up, I believe it could pretty much undo a decade of NIST's efforts in post-quantum cryptography. a seismic shift in the world of cryptography.

No? One of the side effects of running an open competition is that it focused attention on a variety of competing options for this, all of which were formalized, recorded, and publicly evaluated by the world's academic cryptography experts. We're strictly better off as a result, and much of NIST's own work would still be valuable even in a hypothetical scenario in which none of LWE was quantum-safe.
Post reply on HN