Cryptography Reference
In-Depth Information
the reveal phase). We stress that non-obliviousness relates mainly to cheating senders,
because the prescribed sender has no difficulty in later successfully completing the
reveal phase (and in fact, during the commit phase,
S
always convinces the receiver
of this ability). Hence,
any
sender program (not merely the prescribed
S
) that makes
the receiver accept can be modified so that at the end of the commit phase it (locally)
outputs information enabling the reveal phase (i.e.,
and
s
). The modified sender runs
in expected time that is inversely proportional to the probability that the commit phase
is completed successfully.
We remark that in an ordinary commitment scheme, at the end of the commit phase,
the receiver does not necessarily “know” whether or not the sender can later successfully
conduct the reveal phase. For example, a cheating sender in Construction 4.4.2 can
(undetectedly) perform the commit phase without having the ability to later successfully
perform the reveal phase (e.g., the sender may simply send a uniformly chosen string). It
is guaranteed only that if the sender follows the prescribed program, then the sender can
always succeed in the reveal phase. Furthermore, with respect to the scheme presented
in Construction 4.4.4, a cheating sender can (undetectedly) perform the commit phase
in a way that yields a receiver view that does not have any corresponding legal opening
(and hence the reveal phase is doomed to fail); see Exercise 14. Nevertheless, one can
prove the following:
σ
Theorem 4.9.4:
If one-way functions exist, then there exist non-oblivious com-
mitment schemes with a constant number of communication rounds. Furthermore,
the commitment scheme also preserves the secrecy property when applied (poly-
nomially) many times in parallel.
The simultaneous secrecy of many copies is crucial to the application in Section
4.9.2.2.
Proof Idea:
Recall that (ordinary perfectly binding) commitment schemes can
be constructed assuming the existence of one-way functions (see Proposition 4.4.5
and Theorem 3.5.12). Combining such an ordinary commitment scheme with a
zero-knowledge proof of knowledge of information allowing a proper decommit-
ment, we get a non-oblivious commitment scheme. (We remark that such proofs
do exist under the same assumptions; see Section 4.7.) However, the resulting
commitment scheme has an unbounded number of rounds (due to the round
complexity of the zero-knowledge proof), whereas we need a bounded-round
scheme. We seem to have reached a vicious circle, yet there is a way out: We
can use constant-round strong witness-indistinguishable proofs of knowledge,
instead of the zero-knowledge proofs (of knowledge). Such proofs do exist under
the same assumptions; see Section 4.6 and Exercise 28. The resulting commitment
scheme has the additional property that when applied (polynomially) many times
in parallel, the secrecy property holds simultaneously in all copies. This fact fol-
lows from the parallel-composition lemma for (strong) witness-indistinguishable
proofs (see Section 4.6).
