Cryptography Reference
In-Depth Information
log(log(
p
))
1
+
gives an essentially optimal
hard, then one can output many bits. Taking
l
=
asymptotic bit security result for the DLP.
21.6.1 Hard bits for DLP in algebraic group quotients
One can consider hard bits for the DLP in algebraic group quotients. In other words, let
O
i
be a perfect oracle that on input the equivalence class of an element [
g
a
] outputs bit
i
of
a
.
The first problem is that there is more than one value
a
for each class [
g
a
] and so the bit is
not necessarily well-defined.
Section 7 of Li, Naslund and Shparlinski [
349
] considers this problem for LUC. To make
the problem well-defined they consider an element
g
∈ F
p
2
of prime order
r
and an oracle
A
such that
A
(
t
)
=
a
i
where
a
i
is the
i
th bit of
a
for the unique 0
≤
a<r/
2 such that
Tr
F
p
2
/
F
p
(
g
a
). The idea of their method is, given
t
, to compute the two roots
h
1
=
g
a
t
=
g
r
−
a
of
X
2
and
h
2
=
F
p
2
then use previous methods (e.g., Theorem
21.6.3
or
Exercise
21.6.4
) on each of them to compute either
a
or
r
−
tX
+
1in
−
a
(whichever is smaller).
Exercise 21.6.15
Work out the details of the Li, Naslund and Shparlinski result for the
case of the least significant bit of the DLP in LUC.
Exercise 21.6.16
Consider the algebraic group quotient corresponding to elliptic curve
arithmetic using
x
-coordinates only. Fix
P
∈
E
(
F
q
) of prime order
r
.Let
A
be an oracle
that on input
u
∈ F
q
outputs
a
0
where
a
0
is the 0th bit of
a
such that 0
≤
a<r/
2 and
x
([
a
]
P
)
u
. Show that the method of Li, Naslund and Shparlinski can be applied to show
that this bit is a hard bit for the DLP.
=
Li, Naslund and Shparlinski remark that it seems to be hard to obtain a similar result for
XTR. Theorem 3 of Jiang, Xu and Wang [
282
] claims to be such a result, but it does not
seem to be proved in their paper.
21.7 Bit security of Diffie-Hellman
We now consider which bits of the CDH problem are hard. Since the solution to a CDH
instance is a group element it is natural to expect, in contrast with our discussion of the DLP,
that the hardcore bits and the proof techniques depend on which group is being studied.
We first consider the case
g
∈ F
p
where
p
is a large prime and
g
is a primitive root.
Our presentation follows Boneh and Venkatesan [
80
]. We assume every element
x
∈ F
p
is represented as an element of the set
{
1
,
2
,...,p
−
1
}
and we interpret
x
(mod
p
)as
returning a value in this set.
Definition 21.7.1
Let
p
be odd. Let
x
∈{
1
,
2
,...,p
−
1
}
. Define
0if1
≤
x<p/
2
=
MSB
1
(
x
)
1
otherwise.
