Cryptography Reference
In-Depth Information
(denoted
R
). This seems strange, because we do not really want to assume that the real
receiver follows the prescribed program (but rather protect against arbitrary behavior).
The point is that a real receiver may disclose its commit-phase coin tosses at a later
stage, say even after the reveal phase, and by doing so prove
a posteriori
that (at least
in some weak sense) it was following the prescribed program. Actually, the receiver
proves only that it has behaved in a manner that is consistent with its program.
Definition 4.8.7 (Commitment Scheme with Perfect A Posteriori Secrecy):
A
bit-commitment scheme with perfect a posteriori secrecy
is defined as in
Definition 4.8.2, except that the secrecy requirement is replaced by the following
a posteriori secrecy requirement
: For every string r
∈{
,
}
poly(
n
)
, it holds that
0
1
S
(0)
(1
n
)
are statistically close, where R
r
denotes the
execution of the interactive machine R when using internal coin tosses r .
,
R
r
(1
n
)
and
S
(1)
,
R
r
Proposition 4.8.8:
Let
(
I
,
D
,
F
)
be a claw-free collection. Consider a modifica-
tion of Construction 4.8.5 in which the sender's check of whether or not i is in the
range of I
(1
n
)
is omitted (from the commit phase). Then the resulting protocol
constitutes a bit-commitment scheme with perfect a posteriori secrecy.
We stress that in contrast to Proposition 4.8.6, here the claw-free collection need not
have an efficiently recognizable index set. Hence, we had to omit the sender's check.
Yet the receiver can later prove that the message it sent during the commit phase (i.e.,
i
)
is indeed a valid index simply by disclosing the random coins it used in order to generate
i
(using algorithm
I
).
Proof Sketch:
The a posteriori secrecy requirement follows directly from
Property 2 of a claw-free collection (combined with the fact that
i
is indeed
a valid index, since it is generated by invoking
I
). The unambiguity requirement
follows as in Proposition 4.8.6.
A typical application of a commitment scheme with perfect a posteriori secrecy is
presented in Section 4.9.1. In that setting the commitment scheme is used inside an
interactive proof, with the verifier playing the role of the sender (and the prover playing
the role of the receiver). If the verifier a posteriori learns that the prover has been
cheating, then the verifier rejects the input. Hence, no damage is caused, in this case,
by the fact that the secrecy of the verifier's commitments may have been breached.
4.8.3. Perfect Zero-Knowledge Arguments for
NNNP
Having a perfectly hiding commitment scheme at our disposal, we can construct perfect
zero-knowledge arguments for
NP
by modifying the construction of (computational)
NP
zero-knowledge proofs (for
) in a totally syntactic manner. We recall that in these
proof systems (e.g., Construction 4.4.7 for Graph 3-Colorability) the prover uses a
perfectly binding commitment scheme in order to commit itself to many values, some
of which it later reveals upon the verifier's request. All that is needed is to replace
the perfectly binding commitment scheme used by the prover with a perfectly hiding
