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)
