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):
- Sample a random vectors s, and random field elements u, t.
- Sample random group elements C_r and C_2.
- Sample a random challenge γ.
- Set C_a := PedersenCOMM(s; u) - γC_r.
- Set C_1 := PedersenCOMM(<s, b>; t) - γC_2.
- 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):
- Run P' to receive the commitment C_a.
- Run P' to receive the commitments C_r, C_1, and C_2.
- 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.
- Once we have obtained one accepting transcript ((C_r, C_1, C_2), γ, (s, u, t)), we will try for another accepting transcript.
- 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.
- Compute r := (s - s')/(γ - γ').
- 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.