Cryptography Reference
In-Depth Information
Exercise 18.1.8
Prove Theorem
18.1.7
.
[Hint: First pr
ov
e that the analogue of Lemma
18.1.4
in this case is
2
w
−
v
≤
1)
/
(4(
√
2
(2
n/
2
b
n
2
. Then foll
ow the p
roof of Theorem
18.1.6
using the fact
−
−
1))
that
2
(
n
−
1)
/
4
/
√
2
≤
2
n/
4
/
√
2
1
2
1
2
.]
−
+
1
−
Algorithm
25
is the Babai nearest plane algorithm. We use the notation
y
n
=
y
,
w
n
=
w
,
w
etc. Note that Babai's algorithm can be performed using exact arithmetic over
w
n
−
1
=
Q
or using floating-point arithmetic.
Algorithm 25
Babai nearest plane algorithm
INPUT:
{
b
1
,...,
b
n
}
,
w
OUTPUT:
v
Compute Gram-Schmidt basis
b
1
,...,
b
n
Set
w
n
=
w
for
i
n
downto 1
do
Compute
l
i
=
=
w
i
,
b
i
b
i
,
b
i
/
Set
y
i
=
l
i
b
i
)
b
i
−
Set
w
i
−
1
=
w
i
−
(
l
i
−
l
i
l
i
b
i
end for
return
v
=
y
1
+···+
y
n
n
.Let
X
Exercise 18.1.9
Let
{
b
1
,...,
b
n
}
be a basis for a lattice in
Z
∈ R
>
0
be such that
n
. Show that the complexity of the Babai nearest plane algorithm
(not counting LLL) when using exact arithmetic over
b
i
≤
X
for 1
≤
i
≤
is
O
(
n
5
log(
X
)
2
) bit operations.
Q
Exercise 18.1.10
If
is an ordered LLL-reduced basis then
b
1
is likely to be
shorter than
b
n
. It would therefore be more natural to start with
b
1
and define
U
to be the
orthogonal complement of
b
1
. Why is this not possible?
{
b
1
,...,
b
n
}
Example 18.1.11
Consider the LLL-reduced basis
12 3
30
B
=
−
3
3
−
73
3
. We perform the nearest plane method to find a lattice
and the vector
w
=
(10
,
6
,
5)
∈ R
vector close to
w
.
First compute the Gram-Schmidt basis
b
1
=
(1
,
2
,
3),
b
2
=
(24
/
7
,
6
/
7
,
−
12
/
7) and
b
3
=
(10
/
3
,
−
20
/
3
,
10
/
3). Write
37
14
b
1
+
2
b
2
+
20
b
3
.
3
w
=
0 and
w
=
w
=
37
14
b
1
+
2
b
2
=
Since
3
/
20
=
0wehave
y
3
=
(19
/
2
,
7
,
9
/
2). The pro-
w
. Then one takes
y
2
=
cess is continued inductively, so write
w
=
2
b
2
=
(6
,
0
,
−
6) and
