[HN Gopher] A quick post on Chen's algorithm
___________________________________________________________________
A quick post on Chen's algorithm
Author : feross
Score : 57 points
Date : 2024-04-16 20:16 UTC (2 hours ago)
(HTM) web link (blog.cryptographyengineering.com)
(TXT) w3m dump (blog.cryptographyengineering.com)
| glitchc wrote:
| Let's wait for the dust to settle to see if Chen has indeed
| broken the Shortest Vector Problem for lattices. Bold claims
| require strong evidence.
| stoniejohnson wrote:
| Extra-ordinary claims require extra-ordinary evidence!
|
| (my favorite maxim from 2012 era atheism debates on youtube)
|
| But yeah I totally agree. Putting the cart before the horse
| here with the outlined consequences probably isn't smart, but
| to be fair, I haven't (and probably couldn't) read the paper.
| vitus wrote:
| I was under the impression that the Shortest Vector Problem was
| NP hard (at least, in some cases). If this works even in those
| scenarios, that's an even bolder claim by far.
| archgoon wrote:
| Chen has not claimed to have broken SVP; only in certain
| situations. This is a better LLL; not a polynomial hierarchy
| overturning.
| jonahx wrote:
| I appreciate short, accessible writeups on subjects like these.
| faitswulff wrote:
| It seems like the post-quantum algorithm that Signal selected [0]
| involves lattices [1] somehow:
|
| > Kyber is an IND-CCA2-secure key encapsulation mechanism (KEM),
| whose security is based on the hardness of solving the learning-
| with-errors (LWE) problem over module lattices.
|
| Curious to see if Chen's work will eventually lead to Signal
| selecting a different algorithm.
|
| [0]: https://signal.org/blog/pqxdh/
|
| [1]: https://pq-crystals.org/kyber/
| dang wrote:
| Recent and related:
|
| _Quantum Algorithms for Lattice Problems_ -
| https://news.ycombinator.com/item?id=39998396 - April 2024 (118
| comments)
___________________________________________________________________
(page generated 2024-04-16 23:00 UTC)