Hacker News Reader

(of course, this doesn't mean we are in the clear -- a polynomial-time algorithm is alarming)

I don't understand your comment in the context of the previous comment you posted. AIUI, the excerpt says "our algorithm only applies when the modulus q is larger than n^2" where n is 2563 or 2566 (I guess?). So the excerpt would be saying that the algorithm does not apply in this case, because 3000 << (256*3)^2. Right?

If the history of cryptography is any guide, even though this result doesn't break LWE crypto-protocols, it's much more likely now that someone will come up an improvement that will break LWE crypto-protocols. First constructions of algorithms are rarely optimal.

Even though the opposite is possible as well, now that a concrete algorithm has been made. Someone could very well prove that LWE crypto-protocols are secure against some class of algorithms this algorithm belongs to.

Of course, right now, we should just wait for the experts to read the paper and check if there are any problems.

The algorithm is only quantum-polynomial time for a parameter regime not applicable to the PQC candidates.

Reply on news.ycombinator.com