2017.09.07 09:27:07 (905693902241501184) from Daniel J. Bernstein, replying to "JP Aumasson (@veorq)" (905682451565031425):
Looking more closely I see that the paper's cost analyses are wrong even for the non-quantum part: the usual instant-access-to-RAM mistake.
2017.09.07 09:43:45 (905698084600107008) from Daniel J. Bernstein:
"First proof of an actual quantum time speedup": The paper doesn't analyze actual time. For oversimplified "time", 1998 BHT proved speedup.
2017.09.07 08:20:25 (905677114384424960) from Daniel J. Bernstein:
Collisions: https://eprint.iacr.org/2017/847 says time N^0.4 using hardware N^0.2. But parallel rho is better: time N^0.35 using hardware N^0.15.
2017.09.07 08:41:37 (905682451565031425) from "JP Aumasson (@veorq)":
time-space product of 12/25 is interesting, but yeah ignores the cost of QC hardware vs classical, the latency of Q circuits etc.