Cryptography Reference
In-Depth Information
intuition underlying the proof is that it is infeasible to play the iterative hashing so
as to reach a situation in which one can invert
f
on
both
the resulting solutions
y
1
and
y
2
. (We mention that this reasoning fails if one replaces the iterative hashing by an
ordinary one; see Exercise 33.)
4.8.2.3. Construction Based on Claw-Free Collections
A perfectly hiding commitment scheme of
constant number of rounds
can be constructed
using a seemingly stronger intractability assumption, specifically, the existence of claw-
free collections (see Section 2.4.5). This assumption implies the existence of one-way
functions, but it is not known if the converse is true. Nevertheless, claw-free collections
can be constructed under widely believed assumptions such as the intractability of
factoring and DLP. Actually, the construction of perfectly hiding commitment schemes,
presented next, uses a claw-free collection with an additional property; specifically, it
is assumed that the set of indices of the collection (i.e., the range of algorithm
I
) can be
efficiently recognized (i.e., is in
BPP
). Such a collection exists under the assumption
that DLP is intractable (see Section 2.4.5).
Construction 4.8.5 (A Constant-Round Perfectly Hiding Bit Commitment):
Let
(
I
F
)
be a triplet of probabilistic polynomial-time algorithms. (Think
o
f
I as the index generating algorithm of a claw-free collection
{
,
D
,
(
f
i
,
f
i
):
i
∈
I
}
and S and F as the corresponding sampling and evaluating algorithms.)
1.
Commit phase:
To receive a commitment to a bit (using security parameter n),
the receiver randomly generates i
I
(1
n
)
and sends it to the sender. To commit
=
to value
(upon receiving the message i from the receiver), the sender
checks to see if indeed i is in the range of I
(1
n
)
, and if so the sender randomly
generates s
v
∈{
0
,
1
}
=
v,
=
v,
,
s
)
, and sends c to the receiver. (In
case i is not in the range of I
(1
n
)
, the sender aborts the protocol, announcing that
the receiver is cheating.)
2.
(Almost-canonical) reveal phase:
In the reveal phase, it suffices for the sender to re-
veal the string s generated by it in the commit phase. The receiver accepts the value
v
D
(
i
)
, computes c
F
(
i
if F
(
v,
i
,
s
)
=
c, where
(
i
,
c
)
is the receiver's (partial) view of the commit phase.
Proposition 4.8.6:
Let
(
I
,
D
,
F
)
be a claw-free collection with a probabilis-
tic polynomial-time-recognizable set of indices. Then the protocol presented in
Construction 4.8.5 constitutes a perfectly hiding bit-commitment scheme.
Proof Sketch:
The secrecy requirement follows directly from Property 2 of a
claw-free collection (as in Definition 2.4.6) combined with the test
i
∈
I
(1
n
)
conducted by the sender. The unambiguity requirement follows from Property 3 of
a claw-free collection (Definition 2.4.6), using a standard reducibility argument.
(Note that
F
(0
,
i
,
s
0
)
=
F
(1
,
i
,
s
1
) means that (
s
0
,
s
1
) constitute a claw for the
permutation pair (
f
i
,
f
i
).)
