2020.02.04 09:35:25 (1224612412134973441) from Daniel J. Bernstein, replying to "John Schanck (@susurrusus)" (1224483234559549441):
The attacker can build much more attack hardware than the legitimate user, arbitrarily parallelizing the space-2^n attack. The user-verifiable n is small. Aaronson's "faraway skeptic" doesn't impose a nearly low enough latency limit for speed-of-light limits to stop the attack.
2020.02.04 09:42:06 (1224614090326278144) from Daniel J. Bernstein:
After computing the distribution of 2^n outputs (16-bit accuracy is overkill), the attacker samples from the distribution (don't even have to bother adding fake errors given the protocol definition), using a hidden PRNG seed. This directly violates the "certified randomness".
2020.02.04 10:21:01 (1224623886538608640) from Daniel J. Bernstein:
I think I've diagnosed the conceptual mistake that led to this broken protocol. The primary argument for algorithms using vastly more than 2^n time, but less space, is that the legitimate user can't afford 2^n RAM. Conceptual mistake: thinking that attackers can't afford 2^n RAM.
2020.02.03 16:35:34 (1224355757438722048) from "John Schanck (@susurrusus)":
A much better version of this attack, using classical simulation of cost exp(tree width), is credited to Brandão on slide 17. Same slide mentions that the attack significantly reduces min-entropy per round.
2020.02.03 22:03:15 (1224438219212607489) from Daniel J. Bernstein, replying to "John Schanck (@susurrusus)" (1224355757438722048):
That slide claims to be able to extract "10 certified random bits" in "a few seconds", whereas I'm saying that the obvious attack completely breaks the protocol for every n that's feasible to verify. Seems clear that the slide is based on a worse attack. Why do you claim better?
2020.02.04 01:02:07 (1224483234559549441) from "John Schanck (@susurrusus)":
The attack on that slide replaces "standard space-2^n computation of circuit state" with Markov--Shi simulation by tensor network contraction. I haven't seen enough details to believe the "10 certified random bits" claim, but I don't see a complete break.