4 ms·

Quantum Algorithms for Lattice Problems – Update on April 18

169 points by tux3 3y ago

Willingham 3y ago
[flagged]
runiq 3y ago
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.
- mellosouls 3y ago
  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"
  - runiq 3y ago
    No, I did not. Shame on me, and thanks for the heads up!
- boole1854 3y ago
  He has done this, page 37: https://eprint.iacr.org/2024/555.pdf https://eprint.iacr.org/2024/555.pdf
  - runiq 3y ago
    I totally missed that, shame on me. Thanks for the correction!
mellosouls 3y ago
Context, eg: Quantum Algorithms for Lattice Problems,123 comments https://news.ycombinator.com/item?id=39998396 https://news.ycombinator.com/item?id=39998396 and A quick post on Chen's algorithm, 95 comments https://news.ycombinator.com/item?id=40056640 https://news.ycombinator.com/item?id=40056640
deleted 3y ago
[deleted]
kleiba 3y ago
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.
- baby 3y ago
  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.
- boppo1 3y ago
  Yeah, this is the best possible reaction. Dude is cool.
mchusma 3y ago
I love this, great work for science overall. This is exactly the type of approach/response one should take, and I hope he gets praise for doing the right thing.
m3kw9 3y ago
I find it amazing someone can even read and follow all the formulas and find a bug
- hyperbovine 3y ago
  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".
  - brookst 3y ago
    But I do find that amazing?
    - bluejay2387 3y ago
      Me too...
- ncclporterror 3y ago
  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.
  - abdullahkhalids 3y ago
    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.
    - Cyph0n 3y ago
      A second year PhD student no less! He did his undergrad at Tsinghua and is doing a PhD at Berkeley.
  - 3y ago
prestonpitt 3y ago
[flagged]
prestonpitt 3y ago
[flagged]
3PS 3y ago
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.
- vinnyvichy 3y ago
  EDIT: discussion of bug on stack exchange (pointed from Aaronson's blog (mentor of one of the guys who found the bug): https://crypto.stackexchange.com/questions/111385/polynomial-time-quantum-algorithms-for-lattice-problems/111465#111465 https://crypto.stackexchange.com/questions/111385/polynomial... Not only that Yilei annotated with the bug his paper(p37): "Yilei (April 18) Here is the bug: the amplitude of |φ8.f ⟩ does not satisfy M/2 -periodicity. Another way of explaining the bug is: the support of |φ8.f ⟩ contains p1...pκ vectors. After domain extension, we should have got p1p2...pκ · p2...pκ vectors, but as the way |φ8.g⟩ is written, it only contains p1...pκ vectors. So the expression of |φ8.g⟩ is wrong." https://eprint.iacr.org/2024/555.pdf https://eprint.iacr.org/2024/555.pdf
oersted 3y ago
His "comic slides" are fun :) https://eurocrypt.iacr.org/2017/slides/A04-constraint-hiding.pdf https://eurocrypt.iacr.org/2017/slides/A04-constraint-hiding...
Beldin 3y ago
This is a very good reminder that we don't know for various problems whether there is an efficient algorithm. For problems studied for decades (eg travelling salesman) we feel fairly confident that there is no polynomial-time algorithm - but even then, we don't know for sure. As far as I know, the problems underpinning post-quantum cryptography have not yet enjoyed such extensive scrutiny / search for efficient (regular or quantum) algorithms. In other words: stuff that is hoped to be post-quantum might turn out to be quantum -- or even in a feasible non-quantum class. The latter seems unlikely barring p=np-alike breakthroughs, but even these cannot fully be ruled out.

169 points by tux3 3y ago

[flagged]

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.

mellosouls 3y ago
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"
- runiq 3y ago
  No, I did not. Shame on me, and thanks for the heads up!
boole1854 3y ago
He has done this, page 37: https://eprint.iacr.org/2024/555.pdf https://eprint.iacr.org/2024/555.pdf
- runiq 3y ago
  I totally missed that, shame on me. Thanks for the correction!

mellosouls 3y ago

Context, eg: Quantum Algorithms for Lattice Problems,123 comments https://news.ycombinator.com/item?id=39998396 https://news.ycombinator.com/item?id=39998396 and A quick post on Chen's algorithm, 95 comments https://news.ycombinator.com/item?id=40056640 https://news.ycombinator.com/item?id=40056640

deleted 3y ago

[deleted]

kleiba 3y ago

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.

baby 3y ago
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.
boppo1 3y ago
Yeah, this is the best possible reaction. Dude is cool.

mchusma 3y ago

I love this, great work for science overall. This is exactly the type of approach/response one should take, and I hope he gets praise for doing the right thing.

m3kw9 3y ago

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

hyperbovine 3y ago
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".
- brookst 3y ago
  But I do find that amazing?
  - bluejay2387 3y ago
    Me too...
ncclporterror 3y ago
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.
- abdullahkhalids 3y ago
  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.
  - Cyph0n 3y ago
    A second year PhD student no less! He did his undergrad at Tsinghua and is doing a PhD at Berkeley.
- 3y ago

prestonpitt 3y ago

[flagged]

prestonpitt 3y ago

[flagged]

3PS 3y ago

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.

vinnyvichy 3y ago
EDIT: discussion of bug on stack exchange (pointed from Aaronson's blog (mentor of one of the guys who found the bug): https://crypto.stackexchange.com/questions/111385/polynomial-time-quantum-algorithms-for-lattice-problems/111465#111465 https://crypto.stackexchange.com/questions/111385/polynomial... Not only that Yilei annotated with the bug his paper(p37): "Yilei (April 18) Here is the bug: the amplitude of |φ8.f ⟩ does not satisfy M/2 -periodicity. Another way of explaining the bug is: the support of |φ8.f ⟩ contains p1...pκ vectors. After domain extension, we should have got p1p2...pκ · p2...pκ vectors, but as the way |φ8.g⟩ is written, it only contains p1...pκ vectors. So the expression of |φ8.g⟩ is wrong." https://eprint.iacr.org/2024/555.pdf https://eprint.iacr.org/2024/555.pdf

oersted 3y ago

His "comic slides" are fun :) https://eurocrypt.iacr.org/2017/slides/A04-constraint-hiding.pdf https://eurocrypt.iacr.org/2017/slides/A04-constraint-hiding...

Beldin 3y ago

This is a very good reminder that we don't know for various problems whether there is an efficient algorithm. For problems studied for decades (eg travelling salesman) we feel fairly confident that there is no polynomial-time algorithm - but even then, we don't know for sure. As far as I know, the problems underpinning post-quantum cryptography have not yet enjoyed such extensive scrutiny / search for efficient (regular or quantum) algorithms. In other words: stuff that is hoped to be post-quantum might turn out to be quantum -- or even in a feasible non-quantum class. The latter seems unlikely barring p=np-alike breakthroughs, but even these cannot fully be ruled out.