Double trouble proofs

proofs.md

Completeness follows by inspection, so we proceed to sketch out the proofs of knowledge soundness and zero knowledge. We'll start with zero knowledge.

Proof of ZK:

Recall that we want to show that an interaction with the prover reveals no information to the verifier. To do so, we use the "simulation" technique. This involves creating a "simulator" that does not have access to the secret committed vector a, but is still able to output an accepting transcript. Note that since we will compile this protocol with Fiat--Shamir, we only need to prove honest-verifier zero knowledge.

Simulator(public vector b):

1. Sample a random vectors s, and random field elements u, t.
2. Sample random group elements C_r and C_2.
3. Sample a random challenge γ.
4. Set C_a := PedersenCOMM(s; u) - γC_r.
5. Set C_1 := PedersenCOMM(<s, b>; t) - γC_2.
6. Output transcript := ((C_a, C_r, C_1, C_2), γ, (s, u, t)).

Note that the transcript output by Simulator(b) is indistinguishable from that output during an honest execution of (P<->V)(b), as the transcript satisfies all verifier checks. Furthermore, it reveals no information about the actual vector a, as Simulator does not receive it!

Proof of knowledge soundness:

We'll construct an extractor that interacts with, and can rewind, the possibly cheating prover P'.

Extractor(public vector b):

1. Run P' to receive the commitment C_a.
2. Run P' to receive the commitments C_r, C_1, and C_2.
3. Sample a fresh challenge γ, and invoke P'(γ) to obtain (s, u, t). If this does not pass verifier's checks, rewind P' to just after Step 2, and rerun Step 3.
4. Once we have obtained one accepting transcript ((C_r, C_1, C_2), γ, (s, u, t)), we will try for another accepting transcript.
5. Sample a fresh challenge γ', and invoke P'(γ') to obtain (s', u', t'). If this does not pass verifier's checks, rewind P' to just after Step 2, and rerun this step.
6. Compute r := (s - s')/(γ - γ').
7. Output a := s - γr.

This extractor succeeds assuming the hardness of discrete logarithms, as follows. If the verifier's checks pass, then PedersenComm(s) = PedersenComm(a) + γPedersenComm(r). (And similarly for s' and γ'). If PedersenComm is binding, then s = a + γr, and similarly s' = a + γ'r. This allows us to solve for r and then a easily.