Cryptography Reference
In-Depth Information
Proof
In the first half of the proof we consider
t
1
,...,t
n
as fixed values. Later in the proof
we compute a probability over all choices for the
t
i
.
First, note that every vector in the lattice is of the form
l
n
p,β/
2
k
+
1
)
v
=
(
βt
1
−
l
1
p,βt
2
−
l
2
p,...,βt
n
−
for some
β,l
1
,...,l
n
∈ Z
.If
β
≡
α
(mod
p
) then we are done, so suppose now that
β
≡
<p/
2
µ
+
1
, which implies
α
(mod
p
). Suppose also that
v
−
u
|
(
βt
i
(mod
p
))
−
u
i
|
<
p/
2
µ
+
1
for all 1
≤
i
≤
n
. Note that
|
−
|=|
−
u
i
+
u
i
−
|
(
β
α
)
t
i
(mod
p
)
(
βt
i
(mod
p
))
(
αt
i
(mod
p
))
≤|
(
βt
i
(mod
p
))
−
u
i
|+|
(
αt
i
(mod
p
))
−
u
i
|
<p/
2
µ
+
1
p/
2
µ
+
1
p/
2
µ
.
+
=
We now consider
γ
=
(
β
−
α
) as a fixed non-zero element of
F
p
and denote by
A
the
∈ F
p
, that
γt
≡
∈ Z
|
|
<p/
2
µ
and
probability, over all
t
u
(mod
p
)forsome
u
such that
u
=
F
p
it follows that
u
0. Since
γt
is uniformly distributed over
2(
p
<
2
p/
2
µ
2
1
−
1)
+
2
2
1
<
4
A
=
1
≤
2
µ
+
2
µ
.
p
−
p
−
1
2
µ
p
−
Since there are
n
uniformly and independently chosen
t
1
,...,t
n
∈ F
p
the probability
that
<p/
2
µ
for all 1
n
is
A
n
. Finally, there are
p
|
γt
i
(mod
p
)
|
≤
i
≤
−
1 choices for
β
∈{
0
,
1
,...,p
−
1
}
such that
β
≡
α
(mod
p
). Hence, the probability over all such
β
and
<p/
2
µ
+
1
all
t
1
,...,t
n
that
v
−
u
is at most
1)4
n
2
µn
<
2
log
2
(
p
)
+
2
n
2
µn
1)
A
n
<
(
p
−
(
p
−
.
(
log
2
(
p
)
/
2
log
2
(
p
)
1)
A
n
<
2
−
n
. Since
Now,
µn
=
+
3)2
≥
log
2
(
p
)
+
3
n
so (
p
−
n
≥
6 the result follows.
log
2
(
p
)
=
log
2
(
p
)
Corollary 21.7.10
Let p>
2
32
be prime, let n
=
2
and let k
+
log
2
(log
2
(
p
))
. Given
(
t
i
,u
i
=
MSB
k
(
αt
i
))
for
1
≤
i
≤
n as in Definition
21.7.2
one can
compute α in polynomial-time.
Proof
On
e cons
tructs the basis matrix
B
for the lattice
L
in polynomial-time. Note that
n
O
(
√
log(
p
)) so that the matrix requires
O
(log(
p
)
2
) b
it
s storage.
Running the LLL algorithm with factor
δ
=
1
/
√
2 is a polynomial-time computa-
=
1
/
4
+
1
so Remark
17.5.5
should be applied, noting that only
one column has non-integer entries) which returns an LLL-reduced basis. Let
u
be as
above.
The Babai nearest plane algorithm finds
v
such that
n
+
tion (the lattice is not a subset of
Z
<
(1
.
6)2
(
n
+
1)
/
4
√
n
1
p/
2
k
+
1
by Theorem
18.1.7
and Lemma
21.7.8
. This computation requires
O
(log(
p
)
4
.
5
) bit opera-
tions by Exercise
18.1.9
. To apply Theorem
21.7.9
we need the vector
v
output from the
v
−
u
+
