Cryptography Reference
In-Depth Information
perfect zero-knowledge arguments for
can be constructed based on
some reasonable assumptions (33), where perfect zero-knowledge means
that the simulator's output is distributed
identically
to the verifier's
view in the real interaction (see discussion in Section 4.4.2). Note that
stronger security for the prover (as provided by perfect zero-knowledge)
comes at the cost of weaker security for the verifier (as provided by
computational soundness). The answer to the question of whether or
not this trade-off is worthwhile seems to be application dependent,
and one should also take into account the availability and complexity
of the corresponding protocols. (However, as stated in Footnote 1, we
believe that a presentation in terms of proofs should be preferred for
expositional purposes.)
NP
4.4.2
Definitional variations
We consider several definitional issues regarding the notion of zero-
knowledge (as defined in Definition 4.1).
Universal and black-box simulation.
Further strengthening of
Definition 4.1 is obtained by requiring the existence of a
universal sim-
ulator
,denoted
C
, that is given the program of the verifier (i.e.,
B
∗
)
as an auxiliary-input; that is, in terms of Definition 4.1, one should
replace
C
∗
(
x, z
)by
B
∗
B
∗
denotes the description of
the program of
B
∗
(which may depend on
x
and on
z
). That is, we effec-
tively restrict the simulation by requiring that it be a uniform (feasible)
function of the verifier's program (rather than arbitrarily depend on it).
This restriction is very natural, because it seems hard to envision an
alternative way of establishing the zero-knowledge property of a given
protocol. Taking another step, one may argue that since it seems infeas-
ible to reverse-engineer programs, the simulator may as well just use
the verifier strategy as an oracle (or as a “black-box”). This reasoning
gave rise to the notion of
black-box simulation
, which was introduced
and advocated in (71) and further studied in numerous works (see,
e.g., (40)). The belief was that inherent limitations regarding black-
box simulation represent inherent limitations of zero-knowledge itself.
For example, it was believed that the
fact
that the parallel version
C
(
x, z,
), where
