Cryptography Reference
In-Depth Information
2
l
Exercise 21.6.12
Suppose
r
=
−
1 is a Mersenne prime and let
g
have order
r
.Fix
0
l
. Show that if
O
(
g,h
) is a perfect oracle that returns the
i
th bit of the DLP of
h
with respect to
g
then one can compute the whole DLP.
≤
i
≤
To summarise, low order bits of the DLP are always as hard as the DLP, while high
order bits may or may not be hard. However, our examples of cases where the high order
bits are easy are due not to any weakness of the DLP, but rather to statistical properties of
residues modulo
r
. One way to deal with this issue is to define a bit as being “hard” if it
cannot be predicted better than the natural statistical bias (see, for example, Definition 6.1
of Hastad and Naslund [
253
]). However, this approach is less satisfactory for cryptographic
applications if one wants to use the DLP as a source of unpredictable bits. Hence, it is
natural to introduce a more statistically balanced predicate to use in place of high order
bits. In practice, it is often more efficient to compute the least significant bit than to evaluate
this predicate.
g
x
. Define
Exercise 21.6.13
Let
g
have order
r
.Let
f
:
{
0
,
1
,...,r
−
1
}→
G
be
f
(
x
)
=
b
(
x
)
=
0if0
≤
x<r/
2 and
b
(
x
)
=
1if
r/
2
≤
x<r
. Show, using the method of Exer-
cise
21.6.4
, that
b
(
x
) is a hardcore bit for
f
.
We do not cover all results on hard bits for the DLP. See Section 9 of Hastad and
Naslund [
253
] for a general result and further references.
So far we have only discussed showing that single bits of the DLP are hard. There are
several approaches to defining the notion of a set of
k
bits being simultaneously hard. One
definition states that the bits are hard if, for every non-constant function
B
:
{
0
,
1
}
k
→
{
, given an oracle that takes as input
g
x
and computes
B
on the
k
bits of
x
in question,
one can use the oracle to solve the DLP. Another definition, which seems to be more useful
in practice, is in terms of distinguishing the bits from random.
0
,
1
}
n
m
be a one-way function and let
S
Definition 21.6.14
Let
f
:
.
We say the bits labelled by
S
are
simultaneously hard
if there is no polynomial-time
algorithm that given
f
(
x
) can distinguish the sequence (
x
i
:
i
{
0
,
1
}
→{
0
,
1
}
⊂{
1
,...,n
}
∈
S
) from a random #
S
-bit
string.
Peralta [
430
] (using next-bit-predictability instead of hardcore predicates or Defi-
nition
21.6.14
) proves that
O
(log(log(
r
))) least significant bits of the DLP are hard.
Schnorr [
471
] (using Definition
21.6.14
) proves that essentially any
O
(log(log(
r
))) bits
of the DLP are simultaneously hard (using the “bits” of Exercise
21.6.13
for the most
significant bits).
Patel and Sundaram [
428
] showed, under a stronger assumption, that many more bits
are simultaneously hard. Let
g
be an element of prime order
r
,let
l
∈ N
and set
k
=
l
. The ideas of Patel and Sundaram lead to the following result. If, given
g
x
,the
k
least significant bits of
x
are not simultaneously hard then there is an efficient
algorithm to solve the DLP in an interval of length 2
l
(see Exercise
13.3.6
for the definition
of this problem). Hence, under the assumption that the DLP in an interval of length 2
l
is
log
2
(
r
)
−
