Cryptography Reference
In-Depth Information
Lemma 21.7.5
Let p be an odd prime and
1
≤
α<p. Suppose one has a perfect oracle A
such that A
(
t
)
LSB
1
(
αt
(mod
p
))
, where
LSB
1
(
x
)
is the least significant bit of the binary
representation of
0
=
x<p. Then one can compute α using O
(log
2
(
p
))
oracle queries.
Exercise 21.7.6
Prove Lemma
21.7.5
.
≤
Lemmas
21.7.3
and
21.7.5
show that the hidden number problem would be easy if the
values
t
i
in Definition
21.7.2
are chosen adaptively. However, it intuitively seems harder to
solve the hidden number problem when the
t
i
are randomly chosen. On the other hand, as
k
grows the HNP becomes easier, the case
k
being trivial. Hence, one could
hope to be able to solve the HNP as long as
k
is sufficiently large. We now explain the
method of Boneh and Venkatesan [
80
] to solve the HNP using lattices.
=
log
2
(
p
)
n
+
1
Definition 21.7.7
Let (
t
i
,u
i
=
MSB
k
(
αt
i
)) for 1
≤
i
≤
n
. Define a lattice
L
⊆ R
by
the rows of the basis matrix
p
00
···
0
0
0
p
0
0
0
.
.
.
.
B
=
.
000
···
p
0
t
n
1
/
2
k
+
1
t
1
t
2
t
3
···
n
+
1
<p/
2
k
+
1
.
Define the vector
u
=
(
u
1
,u
2
,...,u
n
,
0)
∈ R
where
|
u
i
−
(
αt
i
(mod
p
))
|
p
n
/
2
k
+
1
and there
Lemma 21.7.8
Let L,
u
and n be as in Defini
tion
2
1.7.7
. Then
det(
L
)
=
<
√
n
1
p/
2
k
+
1
.
exists a vector
v
∈
L such that
u
−
v
+
Proof
The first statement is trivial. For the second, note that
u
i
=
MSB
k
(
αt
i
(mod
p
))
p/
2
k
+
1
is the same as saying
αt
i
=
u
i
+
i
+
l
i
p
for some
i
,l
i
∈ Z
such that
|
i
|≤
for
1
≤
i
≤
n
. Now define
v
∈
L
by
l
n
p,α/
2
k
+
1
)
v
=
(
−
l
1
,
−
l
2
,...,
−
l
n
,α
)
B
=
(
αt
1
−
l
1
p,...,αt
n
−
n
,α/
2
k
+
1
)
.
=
(
u
1
+
1
,...,u
n
+
The result follows since
α/
2
k
+
1
<p/
2
k
+
1
.
We now show that, for certain parameters, it is reasonable to expect that any vector in
the lattice
L
that is close to
u
gives the solution
α
.
Theorem 21.7.9
Let p>
2
8
be prime and let α
log
2
(
p
)
∈ F
p
. Let n
=
2
∈N
and let
2
log
2
(
p
)
1
k
∈ R
be such that
log
2
(
p
)
−
1
>k>µ
=
+
3
. Suppose t
1
,...,t
n
are chosen
F
p
and set u
i
=
uniformly and independently at random in
MSB
k
(
αt
i
)
for
1
≤
i
≤
n.
Construct the lattice L as above. Let
u
=
(
u
1
,...,u
n
,
0)
. Then, with probability at least
1
/
2
n
1
−
≥
63
/
64
over all choices for t
1
,...,t
n
, any vector
v
∈
L such that
v
−
u
<
p/
2
µ
+
1
is of the form
(
βt
1
(mod
p
)
,...,βt
n
(mod
p
)
,β/
2
k
+
1
)
=
v
where β
≡
α
(mod
p
)
.
