Cryptography Reference
In-Depth Information
large enough, all vectors
u
(
0
)
j
κ
≤
≤
Hence, if one chooses
,1
j
, are of norm less
than
and give rise to independent vectors
u
j
that are orthogonal to
a
modulo
N
(it is
in fact an LLL-reduced basis of the lattice of such orthogonal vectors). In particular,
taking the inner product of (
12.6
) with
u
j
, we get, for 1
κ
≤
j
≤
,
x
,
u
j
+
c
y
,
u
j
≡
0
(
mod
p
).
(12.8)
Moreover, we can give a heuristic estimate the size of the vectors
u
j
. Assuming
th
at
L
a
b
ehaves like a random lattice, the length of these vectors should be around
√
/
N
1
/
2
π
e
·
since vol
(
L
a
)
=
N
. Neglecting the small multiplicative factor, we
N
1
/
.
can heuristically expect that
u
j
Orthogonalization
For all
j
,let
α
j
=
x
,
u
j
and
β
j
=
y
,
u
j
. We expect to have, for all
j
except the
N
γ
+
1
/
and
N
δ
+
1
/
. Now recall from (
12.8
) that
last few,
|
α
j
|
|
β
j
|
α
j
+
c
·
β
j
≡
0
(
mod
p
).
If
(α
j
,β
j
)
=
(
0
,
0
)
, this amounts to writing
−
c
as the modular ratio
α
j
/β
j
mod
p
.
But this is only possible in general if the sum of the sizes of
α
j
and
β
j
is at least the
size of
p
. In other words, if
N
γ
+
1
/
·
N
δ
+
1
/
p
, that is
2
1
2
,
γ
+
δ
+
(12.9)
we should have
0 for all
j
except perhaps the last few. This means that
u
j
is orthogonal to
x
and
y
in
α
j
=
β
j
=
Z
.
Assume that this does in fact hold for 1
≤
j
≤
−
2, and consider the lattice of
Z
vectors in
orthogonal to
u
j
for 1
≤
j
≤
−
2. This is a bidimensional lattice
x
,
y
)
containing
x
and
y
, and we can find a basis
of it with LLL. This is done by
computing the LLL-reduction of the following lattice in
(
Z
−
2
+
, generated by the
rows of
⎛
⎞
κ
u
1
,
1
···
κ
u
1
10
−
2
,
⎝
.
.
⎠
.
.
.
κ
u
1
,
···
κ
u
−
2
,
01
κ
is a suitably large constant [307].
where
