Cryptography Reference
In-Depth Information
probability is very close to 1). In Section 4.4 it was suggested that the error probability
be reduced to a negligible value by sequentially applying the proof system sufficiently
many times. The problem is that this yields a proof system with a non-constant number
of rounds. A natural suggestion is to perform the repetitions of the basic proof in
parallel, instead of sequentially. The problem with this “solution” is that it is not known
if the resulting proof system is zero-knowledge. Furthermore, it is known that it is not
possible to present, as done in the proof of Proposition 4.4.8, a single simulator that
uses any possible verifier as a black box (see Section 4.5.4). The source of trouble is
that when playing many copies of Construction 4.4.7 in parallel, a cheating verifier
can select the edge to be inspected (i.e., Step V1) in each copy, depending on the
commitments sent in all copies (i.e., in Step P1). Such behavior of the verifier defeats
a simulator analogous to the one presented in the proof of Proposition 4.4.8.
One way to overcome this difficulty is to “switch” the order of Steps P1 and V1. But
switching the order of these steps enables the prover to cheat (by sending commitments
in which only the “query edges” are colored correctly). Hence, a more refined approach
is required. The verifier starts by committing itself to one edge query per each copy (of
Construction 4.4.7), then the prover commits itself to the coloring in each copy, and
only then does the verifier reveal its queries, after which the rest of the proof proceeds
as before. The commitment scheme used by the verifier should prevent the prover from
predicting the sequence of edges committed to by the verifier. This is the point where
the two approaches differ.
1. The first approach uses a perfectly hiding commitment scheme. The problem with this
approach is that such (constant-round) schemes are known to exist only under seem-
ingly stronger assumptions than merely the existence of one-way functions. Yet such
schemes do exist under assumptions such as the intractability of factoring integers or the
intractability of the discrete-logarithm problem.
2. The second approach bounds the computational resources of prospective cheating
provers. Consequently, it suffices to utilize, “against” these provers (as commitment
receivers), commitment schemes with computational security. We remark that this ap-
proach uses (for the commitments by the prover) a commitment scheme with an extra
property. Yet such schemes can be constructed using any one-way function.
Caveat. Both approaches lead to protocols that are zero-knowledge in a liberal sense
(i.e., using expected polynomial-time simulators as defined in Section 4.3.1.6). It is not
known if these protocols (or other round-efficient protocols for
) can be shown to
be zero-knowledge in the strict sense (i.e., using strict probabilistic polynomial-time
simulators).
NP
4.9.1. Using Commitment Schemes with Perfect Secrecy
For the sake of clarity, let us start by presenting a detailed description of the constant-
round interactive proof (for Graph 3-Colorability, G 3 C ) sketched earlier. This in-
teractive proof employs two different commitment schemes. The first scheme is the
simple (perfectly binding) commitment scheme presented in Construction 4.4.2. We
denote by C s (
σ
) the commitment of the sender, using coins s , to the (ternary) value
Search WWH ::




Custom Search