Cryptography Reference
In-Depth Information
F
p
. Then there is no polynomial-time algorithm to compute the k most significant
bits of g
ab
when given g,g
a
and g
b
.
CDH in
Proof
Let (
g,g
a
,g
b
) be an instance of the CDH problem in
g
ab
for
g
and write
α
=
−
=
the solution. We assume that gcd(
b,p
1 (this requirement is removed by Gonzalez
Vasco and Shparlinski [
238
]; other work mentioned below allows
g
to have prime order, in
which case this restriction disappears).
Given a polynomial-time algorithm
A
such that
A
(
g,g
x
,g
y
)
1)
MSB
k
(
g
xy
(mod
p
))
then one can call
A
(
g,g
a
g
r
,g
b
) polynomially many times for uniformly random
r
=
∈
g
br
(mod
p
). Applying Corollary
21.7.10
gives a polynomial-time algorithm to compute
α
.
{
1
,
2
,...,p
−
2
}
to get MSB
k
(
αt
) where
t
=
A number of significant open problems remain:
1. Theorem
21.7.11
shows it is hard to compute all of MSB
k
(
g
ab
) but that does not imply
that, say, MSB
1
(
g
ab
) is hard. A stronger result would be to determine specific hardcore
bits for CDH, or at least to extend the results to MSB
k
for smaller values of
k
. Boneh
and Venkatesan [
81
] give a method that works for
k
=
2 log(log(
p
))
bits (where
g
is
F
p
) but which needs a hint depending on
p
and
g
; they claim this
is a non-uniform result but this depends on the instance generator (see footnote 7 of
Section
21.4.3
). For
k
a primitive root in
=
log(log(
p
))
one can also consider the approach of Nguyen
and Shparlinski [
411
] mentioned above.
Akavia [
8
] uses a totally different approach to prove that MSB
1
is hard for CDH,
but the method is again at best non-uniform (i.e., needs polynomial-sized auxiliary
information depending on
p
and
g
b
).
2. We assumed perfect oracles for computing MSB
k
(
αt
) in the above results. For non-
perfect oracles one can use the above methods to generate a list of candidate values for
g
ab
and then apply the CDH self-corrector of Section
21.3
. We refer to Gonzalez Vasco,
Naslund and Shparlinski [
237
] for details.
The method of Akavia [
8
] also works when the oracle for MSB
1
is unreliable.
3. The above results assumed that
g
is a primitive root modulo
p
, whereas in practice one
chooses
g
to lie in a small subgroup of
F
p
of prime order. The proof of Theorem
21.7.11
F
p
.
Gonzalez Vasco and Shparlinski have given results that apply when the order of
g
is
less than
p
generates values
t
that lie in
g
and so they are not uniformly at random in
1 (see Chapter 14 of [
499
] for details and references). Shparlinski and
Winterhof [
501
,
502
], building on work of Bourgain and Konyagin, have obtained results
when the order of
g
is at least log(
p
)
/
log(log(
p
))
1
−
.
−
Exercise 21.7.12
This exercise concerns a static Diffie-Hellman key exchange protocol
due to Boneh and Venkatesan [
80
] for which one can prove that the most significant bit
is a hardcore bit. Suppose Alice chooses a prime
p
, an integer 1
≤
a<p
−
1 such that
2
a
−
1
1)
(mod
p
). Alice makes
p
and
g
public and
keeps
a
private. When Bob wants to communicate with Alice he sends
g
x
for random
(mod
p
−
gcd(
a,p
−
1)
=
1 and sets
g
=
