3 ms·
So, if I understood correctly, the article seems to say 'learning with errors' problems are now found to be efficiently solvable by quantum algorithms. However
by tux3 4y ago
So, if I understood correctly, the article seems to say 'learning with errors' problems are now found to be efficiently solvable by quantum algorithms.
However, I seem to remember that many NIST post-quantum crypto algorithms are based on variants of LWE problems.
Is this the same sort of LWE problems, or does the new speedup not apply for some other reason?
- tsimionescu 4y agoI think the article is saying that the new class of problem was inspired by LWE, but adds some additional restrictions. Edit: quotes showing this: > Problems like this came to be called “learning with errors,” because the shove and the wind act like a source of random error on the original direction. There is evidence that it is hard to solve for both classical and quantum algorithms. > Yamakawa and Zhandry tweaked the setup. They modified the strength of those starting shoves, making them more predictable. They also caused the wind to be determined by a random oracle so that it was even more random in certain cases but completely dormant in others.