In this note I’ll do a literature review of proofs, including the following topics:
- IP = PSPACE
- AM/MA (public coins)
- ZK-proofs (zero knowledge)
- NIZK, Fiat-Shamir (Can we remove interaction?)
- Doubly-efficient proofs / delegating computation
- Philosophy of how these relate to NCP (?)
High level summary of takeaways:
- interaction is pretty powerful
- there doesn’t appear to be a meaningful way to get rid of interaction for things outside of NP.
- so, this probably has very limited relevance for NCP.
- beyond the observation that IPs should be banned for NCP
- because they dont give mechanistic explanations
Basic IPs
Simplest example:
Prover wants to convince Verifier that two graphs
How to do it:
- V: sends a random permutation of either
. - P: identifies which one it was.
- If P can do this reliably, the graphs must be different.
Remark — you can do parallel repetition here to amplify success pr.
Remark — most complexity theorists suspect that constant round IPs can only do NP.
Public versus private coins Somewhat surprisingly, you can eliminate the need for private random coins by blowing up the number of rounds by a constant factor!
Turns out that there are IP’s for all of PSPACE.
How? “Checksum procedure.”
For simplicity we’ll show an IP for “Sharp-SAT” (TQBF, which is complete for PSPACE, isn’t too much harder, but requires more details which aren’t super relevant to the technique).
The Sharp-SAT problem is, given a formula and a number
Here’s how we’re going to do it.
Fix a formula
The protocol is as follows:
- Ask the Prover for the value of
--- this is supposedly the number of SAT assignment of , if the Prover is being honest. The Prover hands over some number which may or may not actually be . (PS: the prime doesn’t mean derivative) - Ask the Prover to give you coefficients for the degree
polynomial ; the Prover hands over some polynomial which may or may not be . 2. Check that . 3. This ensures that if is a lie, then . - Now, the verifier chooses a random
and tells the prover about it. - Because
is a low degree polynomial, the chance that is pretty low. In particular low enough that we can union bound over all steps of the proof and assume that it never happens.
- Because
- Anyways we kind of just continue on like this.
- The prover sends us
. - We check for consistency with
. - If
was a lie, so if .
- The prover sends us
- Finally at the end the prover will tell us some value
and we can literally just check whether it’s true or not.
ZK proofs for NP Suppose you want to convince me that your graph is 3-Colorable. But you don’t want me to learn anything about the witness. (Note that this problem is NP-complete so if we can have a ZK protocol for it then we also get a ZK protocol for any other problem in NP).
Remark: there are actually even ZK proofs for anything in PSPACE!
Here’s how to do it:
- P: Sends commitments to the values of a coloring (permute the coloring first).
- V: points to a random edge and asks you to open the commitments to the endpoints colors.
- P: does so, and V checks that it is legit.
It should be pretty clear that this is revealing no info.
However, the best success pr you could get if your graph is not actually 3 colorable is like
At this point I should probably actually define ZK:
- For any (potentially malicious) efficient Verifier
- There exists an efficient “simulator
“ - Such that for any
with the property (e.g., a 3-colorable graph), - Such that the following two distributions are comp indistinguishable:
- Output of simulator
- Transcript of interaction between honest Prover
and verifier
- Output of simulator
One important distinction is that there are two kinds of ZK you can talk about:
- ZK with respect to an honest verifier (one that follows the protocol)
- ZK with respect to a malicious verifier (this is what was defined above, and is more interesting)
Okay, so it’s quite easy to argue zero-knowledge versus an Honest Verifier:
We can simulate the transcript as follows:
- First choose the edges the Verifier wants to look at (randomly).
- Then, choose the coloring so that that edge has endpoints of different colors, commit to that coloring, send it, have the Verifier send the edge they want to see, and open the commitment.
If we were willing to do the repetitions in series, then it’d be easy to argue zero-knowledge against a cheating verifier:
- We just repeatedly try to commit to a random coloring,
- hope the verifier picks a good edge,
- and if it doesn’t we rewind and try again.
If we want to do the repetitions in parallel. Then it seems kind of annoying. Somehow you have to say “wlog we can choose the verifier’s edges in advance because the bit commitments are as good as random to them”. But not quite sure how to formalize this.
Another quick super simple example of a ZK proof — QR.
has secret , wants to prove it’s a QR. sends for random asks for either or . sends it.
todo argue that this is legit
NIZK — in the random oracle model
Can we have non-interactive ZK proofs for NP?
Impossible without random oracle assumption (assuming
Now we’re going to assume that we have a public random function
- (In other words, it’s an exponentially long random string.)
- Sometimes you can get away with a shorter random string (e.g., polynomially long). This is called the Common Random String model.
- Think of this random string as the NIST randomness beacon or something.
- Although if we base AI safety on this, and then the AI goes and messes with the source of randomness that we’re using then that’s kind of unfortunate.
- Let’s not worry about that for now.
- Probably it’s best not to think of
as SHA-256; although maybe if you were extremely careful you could get away with something like this. But one reason why SHA256 is not very random is because it’s deterministic and it’s code is just sitting on the internet.
Anyways, here’s the idea, called the Fiat-Shamir protocol:
An interactive (public coin) ZK proof of knowledge of DLOG
- We work over the group
. To be secure, should be bits (i.e., should be exponentially large). ( is prime) should be known to all parties — or else how are they even going to do computation in the group. - There is a public generator
for , and a public value . - Alice has
such that . - DLOG assumption: it’s hard to compute
given only . - Alice would like to convince Bob that she knows
without revealing any info about .
Protocol:
- A: pick
, send - B: Send
- A: Send
- B: Check
Claim 1:
If Alice doesn’t know
Proof:
You can derive
Claim 2:
Bob learns nothing about
Proof
A simulator can start by choosing
Claim 3 You can make this non-interactive, securely, by using the Fiat-Shamir method.
Doubly Efficient proofs (Goldwasser, Kalai, Rothblum https://dl.acm.org/doi/10.1145/2699436)
- Suppose you have a log-space uniform circuit with depth
and input size . - Then there is a (“doubly efficient”) interactive proof where the prover takes time
- And the Verifier takes time
, and the communication complexity is .
Basically you should think of this as, if there’s a computation that can be done in time