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…
Quantum Algorithms for Lattice Problems
11–20 of 127 posts
Re: Quantum Algorithms for Lattice Problems
#12Some initial Reddit discussion here: https://www.reddit.com/r/cryptography/comments/1c0vlfx/the_f...
Re: Quantum Algorithms for Lattice Problems
#13How 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…
Re: Quantum Algorithms for Lattice Problems
#14If 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.
Re: Quantum Algorithms for Lattice Problems
#15Does 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.
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
#16Does 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.
Re: Quantum Algorithms for Lattice Problems
#17Just a bit more improvement and they might be able to use a computer that doesn't exist to break an encrypting scheme nobody uses. Alarming.
Re: Quantum Algorithms for Lattice Problems
#18If 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.
Re: Quantum Algorithms for Lattice Problems
#19Re: Quantum Algorithms for Lattice Problems
#20If 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.