Cryptography Reference
In-Depth Information
4.8.2.2. Construction Based on One-Way Permutations
Perfectly hiding commitment schemes can be constructed using any one-way permuta-
tion. The known scheme, however, involves a linear (in the security parameter) number
of rounds. Hence, it can be used for the purposes of the current section, but not for the
construction in Section 4.9.1.
Construction 4.8.3 (A Perfectly Hiding Bit Commitment):
Let f be a permu-
tation, and let b
(
x
,
y
)
denote the inner product
mod 2
of x and y
(
i.e., b
(
x
,
y
)
=
i
=
1
x
i
y
i
mod 2
, where x
n
n
)
.
=
x
1
···
x
n
∈{
0
,
1
}
and y
=
y
1
···
y
n
∈{
0
,
1
}
1.
Commit phase
(using security parameter n):
(a)
(Local computations):
The receiver randomly selects n
−
1
linearly indepen-
dent vectors r
1
r
n
−
1
n
. The sender uniformly selects s
n
,...,
∈{
0
,
1
}
∈{
0
,
1
}
f
(
s
)
.
(Thus far, no message has been exchanged between the parties.)
(b)
(Iterative hashing):
The parties proceed in n
and computes y
=
−
1
rounds. In the i round
(
i
=
1)
, the receiver sends r
i
1
,...,
n
−
to the sender, which replies by computing
and sending c
i
def
r
i
)
.
(c)
(The “actual” commitment):
At this point there are exactly two solutions to the
system of equations
=
,
b
(
y
{
b
(
y
,
r
i
)
=
c
i
:1
≤
i
≤
n
−
1
}
. (Both parties can easily
determine both solutions.)
The sender sets
π
=
1
if y is the lexicographically first solution (of the
two), and
π
=
0
otherwise.
, the sender sends c
n
def
To commit to a value
v
∈{
0
,
1
}
=
π
⊕
v
to the
receiver.
2.
Canonical reveal phase:
In the reveal phase, the sender reveals
v
along with the
string s randomly selected by it in the commit phase. The receiver accepts the
value
v
if the following two conditions hold, where
((
r
1
,...,
r
n
−
1
)
,
(
c
1
,...,
c
n
))
denote the receiver's view of the commit phase:
r
i
)
c
i
, for all
1
b
(
f
(
s
)
,
=
≤
i
≤
n
−
1
.
If there exists y
<
f
(
s
)(
resp., y
>
f
(
s
))
such that b
(
y
,
r
i
)
c
i
=
for all
1
≤
c
n
c
n
1)
must hold.
That is, the receiver solves the linear system
i
≤
n
−
1
, then
v
=
(
resp.,
v
=
⊕
n
−
1
i
=
1
, obtaining solu-
{
b
(
y
j
,
r
i
)
=
c
i
}
tions y
1
y
2
, so that b
(
y
j
r
i
)
c
i
<
,
=
for j
=
1
,
2
and i
=
1
,...,
n
−
1
. Next, it
checks whether or not f
(
s
)
∈{
y
1
,
y
2
}
(if the answer is negative, it rejects imme-
y
π
). It accepts the value
diately) and sets
π
accordingly (i.e., so that f
(
s
)
=
v
if
c
n
and only if
v
≡
+
π
(mod 2)
.
Proposition 4.8.4:
Suppose that f is a one-way permutation. Then the protocol
presented in Construction 4.8.3 constitutes a perfectly hiding bit-commitment
scheme.
It is quite easy to see that Construction 4.8.3 satisfies the secrecy condition. The proof
that the unambiguity requirement is satisfied is quite complex andis omitted. The
