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

zero-knowledge of such protocols, we use the secrecy of the prover's commitment
scheme and the unambiguity of the verifier's commitment scheme. Hence, only these
properties of the commitment schemes are relevant to the zero-knowledge property
of the protocols. Yet the current (modified) protocol uses commitment schemes with
relevant properties that are not weaker than the ones of the corresponding commitment
schemes used in Construction 4.9.1. Specifically, the prover's commitment scheme in
the modified protocol possesses computational secrecy, just like the prover's commit-
ment scheme in Construction 4.9.1. We stress that this commitment, like the simpler
commitment used for the prover in Construction 4.9.1, has the simultaneous-secrecy (of
many copies) property. Furthermore, the verifier's commitment scheme in the modified
protocol possesses “information-theoretic” unambiguity, whereas the verifier's com-
mitment scheme in Construction 4.9.1 is merely computationally unambiguous. Thus,
using Theorem 4.9.4, we have the following:

Corollary 4.9.5: If non-uniformly one-way functions exist, then every language
in

NP

has a round-efficient zero-knowledge argument.

4.9.2.3. An Alternative Construction

An alternative way of deriving Corollary 4.9.5 is by modifying Construction 4.4.7 so
as to allow easy simulation, and in particular, robustness under parallel composition.
A key ingredient in this modification is the notion of commitment schemes with a
“trapdoor property.” Loosely speaking, the commit phase of such schemes consists of
a receiver message followed by a sender message, so that given the receiver's private
coins one can efficiently generate strings that are computationally indistinguishable
from the sender's message and yet later open these strings so as to reveal any value.
Note that this does not contradict the computational-binding property, since the latter
refers to cheating senders (that do not know the receiver's private coins). We refrain from
presenting a formal definition and merely sketch how such schemes can be constructed
and used.

Constructing a Trapdoor Commitment Scheme Using Any One-Way Function. Let
f be a one-way function, and let R f

def
={ ( f ( w ) ,w ): w ∈{ 0 , 1 } ∗ } be an NP -relation

NP (corresponding to the -set Range( f )). On security parameter n , the receiver se-

n and reduces the instance f ( r ) ∈ Range( f ) to an instance
of the Hamiltonian-cycle (HC) problem, using the standard reduction. The resulting
graph is sent to the sender that (not knowing a Hamiltonian cycle is in it) is asked
to execute Step P1 in Construction 4.7.14 so that it can respond to a Step-V1 mes-
sage that equals its input bit (to which it wishes to commit). That is, to commit to
the bit 0, the sender sends a matrix of commitments to the entries in the adjacency
matrix of a random isomorphic copy of the graph, whereas to commit to the bit 1,
the sender sends a matrix of commitments to the entries in the adjacency matrix of
a random (simple) n -cycle. Hence, the sender behaves analogously to the simula-
tor of Construction 4.7.14. That is repeated, in parallel, for n times, resulting in a
constant-round commitment scheme that is computationally hiding (by virtue of the

lects uniformly r ∈{ 0 , 1 }