The microblog: 2021.06.07 00:37:20

2021.06.07 00:37:20 (1401669565113798657) from Daniel J. Bernstein, replying to "Andre Esser (@4ndre3sser)" (1401536138150481927):

The abstract claims that non-quantum 0.292 is optimal "within a broad class of lattice sieving algorithms covering almost all approaches to date" and that "similar conditional optimality results" apply to the 0.265 "complexity for quantum sieving". Seems rather likely to deceive.

2021.06.08 00:07:44 (1402024501030752263) from Daniel J. Bernstein:

The optimality talk today addressed this issue. The talk didn't challenge the new 0.257 improvement. Instead it seemed to say that the optimality result was for all-pairs algorithms and the 0.257 result isn't an all-pairs algorithm; ergo, no contradiction between the results.


2021.06.02 16:50:54 (1400102632149061633) from Daniel J. Bernstein:

April 2021 posting: says it improves lattice attack exponent 0.265 to 0.257. June 2021 posting, dated April 2021: says 0.265 can't be improved for these algorithms. Sounds like at least one of these teams has some explaining to do.

2021.06.06 15:47:09 (1401536138150481927) from "Andre Esser (@4ndre3sser)":

I think the conditional lower bound only rules out improvements due to improved nearest neighbor search. If the improvement stems from the use of quantum random walks instead of Grover, the works aren't contradicting.