Cryptography Reference
In-Depth Information
Upon receiving the message r ( from the receiver), the sender commits to value
v ∈{
n
0
,
1
}
by uniformly selecting s
∈{
0
,
1
}
and sending G ( s ) if
v =
0 , and
r otherwise.
2. (Canonical) reveal phase: In the reveal phase, the sender reveals the string s used
in the commit phase. The receiver accepts the value 0 if G ( s )
G ( s )
= α
and accepts the
value 1 if G ( s )
r
= α
, where ( r
) is the receiver's view of the commit phase.
Such a definition of the (canonical) reveal phase allows the receiver to accept both
values, but we shall show that that happens very rarely (if at all).
Proposition 4.4.5: If G is a pseudorandom generator, then the protocol presented
in Construction 4.4.4 constitutes a bit-commitment scheme.
Proof: The secrecy requirement follows the fact that G is a pseudorandom gen-
erator. Specifically, let U k denote the random variable uniformly distributed on
strings of length k . Then for every r
∈{
0
,
1
}
3 n , the random variables U 3 n and
U 3 n
r are identically distributed. Hence, if it is feasible to find an r
∈{
0
,
1
}
3 n
such that G ( U n ) and G ( U n )
r are computationally distinguishable, then either
U 3 n and G ( U n ) are computationally distinguishable or U 3 n
r
are computationally distinguishable. In either case, contradiction to the pseudo-
randomness of G follows.
We now turn to the unambiguity requirement. Following the motivating discus-
sion, we call r ∈{ 0 , 1 }
r and G ( U n )
3 n good if the sets { G ( s ): s ∈{ 0 , 1 }
n
} and { G ( s ) r : s
3 n yields a collision between the seeds
s 1 and s 2 if G ( s 1 ) = G ( s 2 ) r . Clearly, r is good if it does not yield a collision
between any pair of seeds. On the other hand, there is at most one string r that
yields a collision between a given pair of seeds ( s 1 , s 2 ); that is, r = G ( s 1 ) G ( s 2 ).
Because there are at most ( 2 n
n
{ 0 , 1 }
} are disjoint. We say that r ∈{ 0 , 1 }
2 ) < 2 2 n possible pairs of seeds, fewer than 2 2 n strings
will yield collisions between pairs of seeds, and so all the other 3 n -bit-long strings
are good. It follows that with probability at least 1 2 2 n 3 n the receiver selects
a good string, in which case its view ( r ) is unambiguous (since if r is good
and G ( s 1 ) = α holds for some s 1 , then G ( s 2 ) = α r must hold for all s 2 's). The
unambiguity requirement follows.
4.4.1.4. Extensions
The definition and the constructions of bit-commitment schemes are easily extended to
general commitment schemes, enabling the sender to commit to a string rather than to a
single bit. Actually, for the purposes of the rest of this section, we need a commitment
scheme by which one can commit to a ternary value. Extending the definition and the
constructions to deal with this special case is even more straightforward.
In the rest of this section we shall need commitment schemes with a seemingly
stronger secrecy requirement than defined earlier. Specifically, instead of requiring
secrecy with respect to all polynomial-time machines, we require secrecy with respect
to all (not necessarily uniform) families of polynomial-size circuits. Assuming the
227
Search WWH ::




Custom Search