Zero-Knowledge Proof Systems - Foundations of Cryptography: Basic Tools - page 323

• In Section 4.5 we discussed the problematics of parallel repetition in the context of zero-
knowledge. As mentioned there, parallel repetition is also problematic in the context of
computationally sound proofs [19] and in the context of multi-prover proofs [74, 190].
• In continuation of Section 4.9, we mention that round-efficient perfect zero-knowledge
arguments for , based on the intractability of the discrete-logarithm problem, have

been published [42].
• In continuation of Section 4.10, we mention that a much more efficient construction
of non-interactive proof systems for

NP

, based on the same assumptions as [76], has
appeared in [144]. Further strengthenings of non-interactive zero-knowledge have been
suggested in [193].
• The paper by Goldwasser, Micali, and Rackoff [124] also contains a suggestion for a
general measure of “knowledge” revealed by a prover. For further details on this measure,
which is called knowledge complexity , see [116] (and the references therein). (Indeed,
knowledge-complexity zero coincides with zero-knowledge.)

NP

Finally, we mention recent research taking place regarding the preservation of zero-
knowledge in settings such as concurrent asynchronous executions [68, 189, 60] and
resettable executions [47]. It would be unwise to attempt to summarize those research
efforts at the current stage.

4.12.3. Open Problems

Our formulation of zero-knowledge (e.g., perfect zero-knowledge as defined in
Definition 4.3.1) is different from the standard definition used in the literature (e.g.,
Definition 4.3.6). The standard definition refers to expected polynomial-time ma-
chines rather than to strictly (probabilistic) polynomial-time machines. Clearly, Defini-
tion 4.3.1 implies Definition 4.3.6 (see Exercise 7), but it is unknown whether or not the
converse holds. In particular, the known constant-round zero-knowledge protocols for
NP

are known to be zero-knowledge only when allowing expected polynomial-time
simulators. This state of affairs is quite annoying, and resolving it will be of theoretical
and practical importance.
Whereas zero-knowledge proofs for

can be constructed based on any (non-
uniformly) one-way function (which is the most general assumption used in this topic),
some other results mentioned earlier require stronger assumptions. Specifically, it would
be nice to construct constant-round zero-knowledge proofs, perfect zero-knowledge
arguments, and non-interactive zero-knowledge proofs for

NP

NP

based on weaker as-

sumptions than the ones currently used.

4.12.4. Exercises

The exercises in this first batch are intended for coverage of the basic material (i.e.,
Sections 4.1-4.4).

Exercise 1: Decreasing the error probability in interactive proof systems: Prove
Proposition 4.2.7.