←back to thread

Computer Scientists Figure Out How to Prove Lies

(www.quantamagazine.org)
15 points pseudolus | 4 comments | 09 Jul 25 23:59 UTC | HN request time: 0.001s | source
Show context
charcircuit ◴[12 Jul 25 04:06 UTC] No.44539213[source]▶
Are they really lies if the grading program considers them correct answers? It sounds like an issue with using a faulty grading program than the protocol.
replies(1): >>44539282 #
1. A1kmm ◴[12 Jul 25 04:21 UTC] No.44539282[source]▶
The problem is that you can construct a proof that there exists a circuit c with hash h = H(c), such that c(x) = y, where h & y are public, and c and x is private. That is a bad thing if you can construct such a proof when it isn't actually true, for certain specially crafted c.
replies(1): >>44539435 #
2. charcircuit ◴[12 Jul 25 05:01 UTC] No.44539435[source]▶
What value is such a proof of you don't know what the circuit is?
replies(1): >>44539882 #
3. A1kmm ◴[12 Jul 25 06:42 UTC] No.44539882[source]▶
It depends what the proof system is being used for. There are applications of ZKC that this would absolutely break.

It isn't on the exact same proving scheme broken in this research, but consider https://risczero.com/blog/zkpoex, which is about proving that you have an exploit (a program) that puts a protocol into into an unexpected state, without revealing the exploit. Imagine you had a specially crafted program that allows you to prove you have an exploit, but actually none exists, and it is just that you're computing the same hash in your program that is used in the Fiat-Shamir heuristic, and violating the assumptions of the random oracle model.

replies(1): >>44540316 #
4. charcircuit ◴[12 Jul 25 08:30 UTC] No.44540316{3}[source]▶
And why should people trust the program is not computing the hash? If people don't have a way to trust it then of course it can be gamed. This article doesn't sound like a new result, it's just people not verifying that programs aren't gaming the system.