Cryptography Reference
In-Depth Information
Proof
Let
A
be a perfect oracle that on input (
g,g
a
) outputs the least significant bit of
0
a<r
. In other words, if the binary expansion of
a
is
i
=
0
a
i
2
i
then
A
outputs
a
0
.We
will use
A
to compute
a
.
Thefirststepistocall
A
(
g,h
) to get
a
0
. Once this has been obtained we set
h
=
≤
hg
−
a
0
.
Then
h
=
g
2
a
1
+
4
a
2
+···
.Let
u
2
−
1
=
=
(
r
+
1)
/
2(mod
r
) and define
(
h
)
u
.
h
1
=
g
a
1
+
2
a
2
+···
Then
h
1
=
so calling
A
(
g,h
1
)gives
a
1
.For
i
=
2
,
3
,...
compute
h
i
=
(
h
i
−
1
g
−
a
i
−
1
)
u
and
a
i
=
A
(
g,h
i
), which computes the binary expansion of
a
. This reduction
runs in polynomial-time and requires polynomially many calls to the oracle
A
.
Exercise 21.6.4
Give an alternative proof of Theorem
21.6.3
based on bounding the
unknown
a
in the range
1)
r/
2
j
a<lr/
2
j
.
(
l
−
≤
1)
r/
2
j
a<lr/
2
j
and if
Initially, one sets
l
=
1 and
j
=
0. At step
j
, if one has (
l
−
≤
1)
r/
2
j
+
1
a/
2
<lr/
2
j
+
1
and if
a
is odd then (2
j
1)
r/
2
j
+
1
a
is even then (
l
−
≤
+
l
−
≤
+
r
)
/
2
<
(2
j
+
l
)
r/
2
j
+
1
. Show that when
j
=
one can compute 2
−
j
a
(mod
r
)
(
a
log
2
(
r
)
exactly and hence deduce
a
.
Exercise 21.6.5
Since one can correctly guess the least significant bit of the DLP with
probability 1/2, why does Theorem
21.6.3
not prove that DLP is easy?
One should also consider the case of a DL-LSB oracle that only works with some
noticeable probability
. It is then necessary to randomise the calls to the oracle, but the
problem is to determine the LSB of
a
given the LSBs of some algebraically related values.
The trick is to guess some
u
=
O
(log(1
/
))
=
O
(log(log(
r
))) most significant bits of
a
and
g
a
where the
u
most significant bits of
a
are zero).
One can then call the oracle on
h
g
y
for random 0
set them to zero (i.e., replace
h
by
h
=
r/
2
u
and take a majority vote
to get the result. For details of the argument see Blum and Micali [
68
].
We conclude that computing the LSB of the DLP is as hard as computing the whole
DLP; such bits are called
hardcore bits
.
≤
y
≤
r
−
}
∗
be a function computable in polynomial-time
(i.e., there is some polynomial
p
(
n
) such that for
x
}
∗
→{
Definition 21.6.6
Let
f
:
{
0
,
1
0
,
1
n
one can compute
f
(
x
)inat
∈{
0
,
1
}
{
}
∗
→{
}
most
p
(
n
) bit operations). A function
b
:
is a
hardcore bit
or
hardcore
predicate
for
f
if, for all probabilistic polynomial-time algorithms
A
,the
advantage
Adv
x
∈{
0
,
1
}
n
A
(
f
(
x
))
0
,
1
0
,
1
b
(
x
)
=
is negligible as a function of
n
.
We now give some candidate hardcore predicates for the DLP. We also restate the
meaning of hardcore bit for functions defined on
}
∗
.
{
0
,
1
,...,r
−
1
}
rather than
{
0
,
1
