Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quantum Algorithms for Lattice Problems – Update on April 18

chenyilei.net

Post reply on HN
Print view View original

11–20 of 28 posts

Re: Quantum Algorithms for Lattice Problems – Update on April 18

#11

Post by runiq »

mellosouls wrote: post #5
runiq wrote: post #3

I hope the author will post an official correction/amendment to the original paper and not just leave a short notice on their personal homepage.

Did you check the paper they describe in the note? "See the updated version of eprint/2024/555 - Section 3.5.9 (Page 37) for details"

No, I did not. Shame on me, and thanks for the heads up!

Re: Quantum Algorithms for Lattice Problems – Update on April 18

#12

Post by runiq »

boole1854 wrote: post #6
runiq wrote: post #3

I hope the author will post an official correction/amendment to the original paper and not just leave a short notice on their personal homepage.

He has done this, page 37: https://eprint.iacr.org/2024/555.pdf

I totally missed that, shame on me. Thanks for the correction!

Re: Quantum Algorithms for Lattice Problems – Update on April 18

#13

Post by baby »

kleiba wrote: post #8

I find that this is a great reaction to someone finding a bug in your paper. No trying to cover it up, but straight-up admitting a mistake. Also, the fact that he leaves the paper out because it does contain novel ideas that might be useful for further research is cool.

I had a similar thing happened to a paper of mine at the start of my career. Someone found an issue and published a paper to attack my paper. I felt like shit for a long time and thought about retracting. But then decided that my paper actually contained a lot of cool stuff, and so published an update with text highlighted in ted throughout the paper talking about the attack and about the sections that became obsolete.

In retrospect I’m really happy I did the right thing. It can be nerve wracking to publish something that ends up being wrong, but being transparent and not taking things personally, and understanding that whatever happened is still providing value to a lot of people, is the right path.

Re: Quantum Algorithms for Lattice Problems – Update on April 18

#16

Post by 3PS »

Condolences to the author, but this is a huge relief. A polytime quantum algorithm for LWE would have been a scary prospect for the future of asymmetric key crypto. (Not to mention all the other cool stuff people are building on top like fully homomorphic encryption.) Even if it wasn't quite fast enough to break the current schemes that NIST is standardizing, I (and I'm sure many others) would much prefer those problems to stay in exptime.

Re: Quantum Algorithms for Lattice Problems – Update on April 18

#17

Post by hyperbovine »

m3kw9 wrote: post #10

I find it amazing someone can even read and follow all the formulas and find a bug

They have spent thousands, if not tens of thousands, of hours building this skill set. It's like saying "I find it amazing that someone can play Scriabin's piano sonata no. 5 perfectly".

Re: Quantum Algorithms for Lattice Problems – Update on April 18

#19

Post by ncclporterror »

m3kw9 wrote: post #10

I find it amazing someone can even read and follow all the formulas and find a bug

The CV of Thomas Vidick, one of the two people that found the bug, is quite impressive. Undergrad at ENS in France (ranked 1st), PhD at Berkeley (3.97/4.0), postdoc at MIT under Scott Aaronson, and now full professor at Caltech. He literally wrote a book on the topic (Introduction to Quantum Cryptography). So, yeah.

Re: Quantum Algorithms for Lattice Problems – Update on April 18

#20

Post by abdullahkhalids »

ncclporterror wrote: post #19
m3kw9 wrote: post #10

I find it amazing someone can even read and follow all the formulas and find a bug

The CV of Thomas Vidick, one of the two people that found the bug, is quite impressive. Undergrad at ENS in France (ranked 1st), PhD at Berkeley (3.97/4.0), postdoc at MIT under Scott Aaronson, and now full professor at Caltech. He literally wrote a book on the topic (Introduction to Quantum Cryptography). So, yeah.

The other person to find the bug is currently a PhD student, which is more impressive. They beat all the other experts reading the paper.
Post reply on HN