2020.02.04 18:04:10 (1224740440160731136) from Daniel J. Bernstein, replying to "John Schanck (@susurrusus)" (1224735804393709574):
IBM's "2.5 days" is bottlenecked by _disk_, precisely because they don't have enough RAM (which would cost roughly $100 million). "Treewidth" on slide 17 sounds like an allusion to vastly slower algorithms: Google estimates 10000 years for these circuits. Why do you claim faster?
2020.02.04 18:09:17 (1224741730941112320) from Daniel J. Bernstein:
And, to be clear, the arxiv paper that you cite is one of the vastly slower algorithms for these circuits. Google skipped the obvious much faster algorithm because they didn't realize space 2^53 is feasible; this is questionable for legitimate users and wrong for attackers.
2020.02.04 15:52:12 (1224707230550974464) from "John Schanck (@susurrusus)", replying to "John Schanck (@susurrusus)" (1224707187571818504):
There's an existing security claim relative to the standard parallel attack. So where's the conceptual error? Obviously there's room for debate on whether ms/round latency is low enough, but that's in scope prior to your tweet.
2020.02.04 16:49:22 (1224721615717617665) from Daniel J. Bernstein, replying to "John Schanck (@susurrusus)" (1224707230550974464):
You have the attack ordering backwards. One can massively slow down the obvious attack by replacing RAM with disk and it still takes (for n=53, as per IBM vs. Google) only a few days where the "better" attack takes 10000 years. RAM + special-purpose chips would be milliseconds.
2020.02.04 16:52:48 (1224722481929428992) from Daniel J. Bernstein:
Regarding the algorithm details, it should be obvious that recomputing a path is slower than caching it, and all of the low-memory algorithms have _tons_ of recomputation. Aaronson is talking about (and claims that Google has) generic enough circuits that 2^n is the speed record.
2020.02.04 17:45:44 (1224735804393709574) from "John Schanck (@susurrusus)":
I do not have the attack ordering backwards. My understanding of Slide 17 was that the existing security claim is relative to an attack machine like arXiv:1905.00444. The question is whether RAM + special-purpose chips → milliseconds when RAM + GPUs → days.