Cryptography Reference
In-Depth Information
prover's commitments in Step P1 of Construction 4.7.14) and computationally binding
(since otherwise the sender recovers
r
and so inverts
f
on input
f
(
r
)). In contrast,
knowledge of
r
allows one to execute the prover's strategy for Step P1 of Construc-
tion 4.7.14 and later open the commitment either way. (Note that the standard reduc-
tion of Range(
f
) to HC is augmented by a polynomial-time computable and invertible
mapping of pre-images under
f
to Hamiltonian cycles in the corresponding reduced
graphs.)
Using the Trapdoor Commitment Scheme.
One way of using the foregoing scheme
toward our goals is to use it for the prover's commitment in (Step P1 of) Construc-
tion 4.4.7. To this end, we augment the trapdoor commitment scheme so that before
the sender sends its actual commitment (i.e., the message corresponding to Step P1 of
Construction 4.7.14) we let the receiver prove that it knows a (corresponding) trapdoor
(i.e., a sequence of coins that yields the graph it has sent to the sender). This proof
of knowledge need only be witness-hiding, and so it can be carried out in a constant
number of rounds. The simulator for the foregoing modification of Construction 4.4.7
first uses the corresponding knowledge extractor (to obtain the trapdoor for the prover's
commitments) and then takes advantage of the trapdoor feature to generate false com-
mitments that it can later open any way it needs to (so as to answer the verifier's
requests).
4.10.
∗
Non-Interactive Zero-Knowledge Proofs
In this section we consider non-interactive zero-knowledge proof systems. The model
consists of three entities: a prover, a verifier, and a uniformly selected sequence of
bits (which can be thought of as being selected by a trusted third party). Both verifier
and prover can read the random sequence, and each can toss additional coins. The
interaction consists of a single message sent from the prover to the verifier, who then is
left with the decision (whether to accept or not). Non-interactive zero-knowledge proof
systems have various applications (e.g., to encryption schemes secure against chosen
message attacks and to signature schemes).
We start with basic definitions and constructions allowing us to prove a single as-
sertion of a priori bounded length. Next we extend the treatment to proof systems in
which many assertions of various lengths can be proved, as long as the total length of
all assertions is a polynomial in a security parameter but the polynomial is
not
a priori
known. Jumping ahead, we note that, unlike the basic treatment, the extended treatment
allows us to prove assertions of total length much greater than the length of the trusted
random string. The relation between the total length of the provable assertions and the
length of the trusted random string is analogous to the relation between the total length
of messages that can be encrypted (resp., documents that can be signed) and the length
of the encryption key (resp., signing key). We stress, however, that even handling the
basic case is very challenging in the current context (of non-interactive zero-knowledge
proofs).
