Daniel J. Bernstein on Nostr: Looks like Aparne Gupte, Seyoon Ragavan, and Mark Zhandry have a computer-checked ...
Published at
2026-08-15 06:22:19 UTCEvent JSON
{
"id": "97fda253f578adccd29ed4e34bba3ddc1a9dfbdf7a0cfec8b57dbfe32cfe2d9e",
"pubkey": "dfc7d34aef2cd15aa9eb1c20d755dbf8cafb7bbd155f737c941e14d8c3c1f95a",
"created_at": 1786774939,
"kind": 1,
"tags": [
[
"proxy",
"https://mastodon.cr.yp.to/users/djb/statuses/117098082438225574",
"activitypub"
],
[
"client",
"Mostr",
"31990:6be38f8c63df7dbf84db7ec4a6e6fbbd8d19dca3b980efad18585c46f04b26f9:mostr",
"wss://relay.ditto.pub"
]
],
"content": "Looks like Aparne Gupte, Seyoon Ragavan, and Mark Zhandry have a computer-checked proof that Simon's DCP algorithm has cost/probability ratio _at least_ 2^(n/9): https://github.com/sragavan99/lean-ePrint-2026-1591-refutation For comparison, Regev's approach plus https://eprint.iacr.org/2020/168 seems to be around 2^(2n/9).",
"sig": "177ff73dfc14859343e605869517c6bd34ac7d2491852d5221165b0126e5c3340f68ee183a00411d622c57f22194d721dd226d52785d6d5f17447e4d10b7d5ec"
}
