This is a similar (and further) question of Verification of Pinocchio (verifiable computation)

In Section 2.1, it said

the outsourced computation is a function, $F(u,w)$, of two inputs: the client’s input $u$ and an auxiliary input $w$ from the worker. A VC scheme is zeroknowledge if the client learns nothing about the worker’s input

But in section 3.1, Protocol 2, the verification function requires all the elements $c_k$, which I think contain the value of all the input wires (including $w$). So how can it hide $w$ from the client? The Zero Knowledge section said that the GGPR’s rerandomization technique could be used, but the rerandomization is only added to $v(x),w(x),r(x)$, and I guess the client still have to know all the $c_k$?

I've been confused on this for days. Can anyone please help me to understand how the ZK is done?


It is true that the verification procedure needs the values of the input wires, but "input wires" refers only to the wires of $u$, the value provided by the client. The wires for $w$ are considered "middle wires", and are included in the computation of $v_{mid}$, $w_{mid}$, and $y_{mid}$ (i.e., their indices are included in $I_{mid}$).

On a higher level, the protocol does this:

The client sends (to the worker) values for some (not necessarily all, and possibly even zero) wires. The wires for which a value is provided by the client are called the "input wires".

The worker sends (to the client) two things:

  1. Values for some wires of the circuit whose values have not been provided by the client. The wires for which a value is provided by the worker are called "output wires". All wires that are not input or output wires are called "middle wires".

  2. A proof of the following statement: It is possible to assign values to all the middle wires of the circuit so that "everything works", meaning that the input and output wires for every gate of the circuit are correct for the operation that the gate is supposed to perform, and moreover, the worker knows some such values. This proof can be zero-knowledge; in that case it reveals nothing about the values of the middle wires.

The case where "input wires" (resp. "output wires") in the above sense correspond to the input and output wires of the circuit in the usual sense is actually just a special case, which corresponds to the "non-ZK" case discussed in the paper. In the ZK case discussed in the paper, the "input wires" in the above sense correspond to only some of the input wires of the circuit: the wires for $u$. The wires for $w$ are "middle wires", so that the worker proves, in zero-knowlege, that it knows appropriate values for those wires.

  • $\begingroup$ Thank you, it's exactly what I want to know. But I am still not very clear on how to attach $w$ to the middle wire? Take the circuit in Figure.2 for example:$c_6=(c_1+c_2)*(c_3*c_4)$, $c_1,c_2,c_3,c_4,c_6$ are the input wires, and $c_5=c_3*c_4$ is the middle wire. The value of $c_5$ is determined by the input, and cannot be used to represent $w$. e.g now the worker wants to compute $F(u_1,u_2,u_3,w) = (u_1+u_2)*(u_3*w)$, how to make a circuit that hides $w$ in the middle wires? $\endgroup$ – vince.h.c Feb 11 '17 at 9:50
  • $\begingroup$ It is important to distinguish between the input/output/middle wires of the circuit in the usual sense, and in the sense I described above. If you want to treat wire $4$ as a middle wire, you just include $4 \in I_{mid}$. $\endgroup$ – fkraiem Feb 11 '17 at 9:59
  • $\begingroup$ Thanks, I think I can have a good sleep tonight, lol. I wonder why the author don't give it more description in the paper. $\endgroup$ – vince.h.c Feb 11 '17 at 10:16
  • 1
    $\begingroup$ The Pinocchio paper builds heavily on the previous paper of Gennaro et al., so some details which appeared there are not repeated... $\endgroup$ – fkraiem Feb 11 '17 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.