Cryptography Reference

In-Depth Information

probability, provided that (conditioned on producing out-

put) the output is computationally indistinguishable from

the desired distribution (i.e., the view of the cheating verifier

in a real interaction). This is the case because, by repeatedly

invoking this weak simulator (polynomially) many times, we

may obtain a simulator that fails to produce an output with

negligible probability. Finally, letting the simulator produce

an arbitrary output rather than failing, we obtain a simulator

that never fails (as required by the definition), while skewing

the output distribution by at most a negligible amount.

Our simulator starts by selecting uniformly and independently a ran-

dom color (i.e., element of

) for each vertex, and feeding the

verifier strategy with random commitments to these random colors.

Indeed, the simulator feeds the verifier with a distribution that is very

different from the distribution that the verifier sees in a real interaction

with the prover. However, being computationally-restricted the verifier

cannot tell these distributions apart (or else we obtain a contradiction

to the security of the commitment scheme in use). Now, if the verifier

asks to inspect an edge that is properly colored then the simulator per-

forms the proper decommitment action and outputs the transcript of

this interaction. Otherwise, the simulator halts proclaiming failure. We

claim that failure occurs with probability approximately 1
/
3(orelse

we obtain a contradiction to the security of the commitment scheme

in use). Furthermore, based on the same hypothesis (but via a more

complex proof (cf. (65, Sec. 4.4.2.3))), conditioned on not failing, the

output of the simulator is computationally indistinguishable from the

verifier's view of the real interaction.

{

1
,
2
,
3

}

Commitment schemes.
Loosely speaking, commitment schemes

are two-stage (two-party) protocols allowing for one party to commit

itself (at the first stage) to a value while keeping the value secret. In

a (second) latter stage, the commitment is “opened” and it is guaran-

teed that the “opening” can yield only a single value determined in the

committing phase. Thus, the (first stage of the) commitment scheme

is both
binding
and
hiding
. A simple (uni-directional communication)