Cryptography Reference
In-Depth Information
⎛
⎝
⎞
⎠
2
+
1
q
0
···
00
.
.
02
+
1
q
.
.
.
.
.
.
.
.
.
.
.
.
0
02
+
1
q
0
0
...
2
+
1
t
1
2
+
1
t
d
1
... ...
2
+
1
2
+
1
implies the existence of an integer
c
i
such
The inequality
|
v
i
/
−
α
t
i
|
q
≤
q
/
that
2
+
1
t
i
−
2
+
1
qc
i
|≤
|
v
i
−
α
·
q
.
(12.3)
Note then that the row vector
=
α
·
2
+
1
t
1
+
2
+
1
q
2
+
1
t
d
+
2
+
1
q
c
c
1
·
,...,α
·
c
d
·
,α)
α
belongs to
L
, since it can be obtained by multiplying the last row vector by
and then
subtracting appropriate multiples of the first
d
row vectors. Since the last coordinate
of this vector discloses the hidden number
, we call
c
the
hidden vector
. The hidden
vector is very close to the (publicly known) row vector
v
α
. Indeed,
by (
12.3
), the distance from
c
to
v
(in the Euclidean norm, say) is bounded by
=
(
v
1
,...,
v
d
,
0
)
q
√
d
v
−
c
≤
+
1
.
q
d
. Therefore, assuming heuristically
that
L
behaves like a random lattice, Eq. (
12.1
) suggests that the length of the shortest
vector in
L
should be
2
(
+
1
)
d
On the other hand, one has vol
(
L
)
=
·
d
d
+
1
+
1
1
/
d
+
1
2
(
+
1
)
d
/(
d
+
1
)
q
d
/(
d
+
1
)
.
λ
1
(
L
)
≈
vol
(
L
)
=
e
·
2
π
e
2
π
If
is much shorter than this length, we expect
c
to be the closest vector to
v
in
L
. This is realized when
v
−
c
d
q
√
d
+
1
2
(
+
1
)
d
/(
d
+
1
)
q
d
/(
d
+
1
)
+
1
e
·
2
π
or equivalently
d
2
√
π
q
.
e
/
2
If
q
is
N
bits long, this is satisfied for
N
d
log
2
√
π
2
.
−
e
/
