Cryptography Reference
In-Depth Information
=
log
2
(
p
)
/
2
Babai algorithm to be within
p/
2
µ
+
1
of
u
where
µ
+
3. Hence, we need
(1
.
6)2
(
n
+
1)
/
4
√
n
+
1
1
2
µ
+
1
,
<
2
k
+
1
log
2
(
√
n
log
2
(
p
)
which is
µ
+
log
2
(1
.
6)
+
(
n
+
1)
/
4
+
+
1)
<k
=
+
log
2
(log
2
(
p
))
.
Since
log
2
(
√
n
log
2
(
p
)
1
µ
+
log
2
(1
.
6)
+
(
n
+
1)
/
4
+
+
1)
≤
+
3
.
95
+
2
log
2
(
n
+
1)
the result follows whenever
p
is sufficiently large (the reader can check that
p>
2
32
is
sufficient).
It follows from Theorem
21.7.9
that, with probability at least 63
/
64 the vector
v
=
n
+
1
, output by the Babai algorithm is such that
v
n
+
1
2
k
+
1
(
v
1
,...,v
n
+
1
)
∈ R
≡
α
(mod
p
).
It follows that the hidden number
α
can be efficiently computed.
2
160
9
.
32. In practice, the algorithm works well for primes
of this size. For example, Howgrave-Graham and Smart [
270
] present results of practical
experiments where 8 of the most significant bi
ts are p
rovided by an oracle. We stress that
these results do not show that all of the
k
Note that if
p
≈
then
µ
≈
=
log
2
(
p
)
most significant
bits are hard. Instead, one can only deduce that there is a predicate defined on these
k
bits
that is a hardcore predicate for CDH.
Nguyen and Shparlinski [
411
] also remark that one could use other methods than LLL
and the Babai nearest plane algorithm. They show that if one uses the Ajtai, Kumar and
Sivakumar algorithm for CVP then one only needs
k
+
log
2
(log
2
(
p
))
bits to obtain an
algorithm for the hidden number problem with complexity of
p
O
(1
/
log(log(
p
)))
bit operations.
They further show that if one has a perfect oracle for CVP (with respect to the
∞
norm)
then one can solve the hidden number problem in polynomial-time given only
k
=
log(log(
p
))
=
1
+
bits for any
>
0.
One final remark, the methods in this section assume a perfect oracle that outputs
MSB
1
(
αt
(mod
p
)). Since there seems to be no way to determine whether the output of
the oracle is correct, it is an open problem to get results in the presence of an oracle that
sometimes makes mistakes. For further discussion and applications of the hidden number
problem see Shparlinski [
500
].
21.7.2 Hard bits for CDH modulo a prime
We can finally state a result about hard bits for CDH.
Th
eorem
21.7.11
Let p>
2
32
be prime, let g be a primitive root modulo p and let k
=
log
2
(
p
)
+
log
2
(log
2
(
p
))
. Suppose there is no polynomial-time algorithm to solve
11
11
As we have seen, to make such a statement precise one needs an instance generator that outputs groups from a family.
