Cryptography Reference
In-Depth Information
12.4.4 Multiple-Fault Attack
We now describe the multiple-fault attack of [108], which uses lattices in a very
different way. We are now given
faulty signatures, and in particular a vector
a
=
(
a
1
,...,
a
)
of integers such that, for two short unknown vectors
x
=
(
x
1
,...,
x
)
and
y
=
(
y
1
,...,
y
)
,wehave:
a
+
x
+
c
·
y
≡
0
(
mod
p
).
(12.6)
The attack then proceeds in three steps.
Linearization
The first step is to eliminate
a
in (
12.6
) to obtain a linear relation. To do so, we try
to find vectors
u
j
orthogonal to
a
modulo
N
, and take the inner products of (
12.6
)
with the
u
j
's.
The set
L
a
={
∈ Z
:
,
≡
(
)
}
u
a
u
0
mod
N
of vectors
u
orthogonal to
a
modulo
Z
of rank
and volume
N
, as seen in Sect.
12.2.3
. It is possible to
find a reduced basis of it by standard orthogonal lattice techniques [307] as follows.
Denote by
L
(
0
)
N
is a lattice in
Z
+
1
generated by the rows of the matrix
⎛
the lattice in
a
⎞
κ
N
0
··· ···
0
⎝
⎠
κ
a
1
10
···
0
.
a
2
01
.
.
.
κ
(12.7)
.
.
.
.
.
.
.
.
0
κ
a
0
···
01
is a large scaling constant. Now for any vector
u
(
0
)
=
(
where
κ
u
0
,
u
1
,...,
u
)
in this
lattice, one has
u
0
=
κ(
a
1
u
1
+···+
a
u
+
mN
)
for some integer
m
. In particular,
if
|
u
0
|
<κ
, then
u
0
=
0, and
u
=
(
u
1
,...,
u
)
must satisfy
a
,
u
≡
0
(
mod
N
)
.
Thus, any vector
u
(
0
)
in
L
(
0
)
whose norm is less than
κ
gives rise to a vector
u
∈
L
a
.
a
is in
L
(
0
)
Conversely, if
u
is a point in
L
a
, then
u
(
0
)
=
(
0
,
u
1
,...,
u
)
.
a
Z
Z
Since it admits
N
as a sublattice, the lattice
L
a
in
contains a linearly inde-
pendent family consisting of
vectors of length at most
N
. Taking the corresponding
vectors in
L
(
0
)
L
(
0
)
, this implies that
λ
j
(
)
≤
N
for 1
≤
j
≤
.
a
a
u
(
0
)
1
u
(
0
)
+
of
L
(
0
)
Consider then an LLL-reduced basis
(
,...,
1
)
. Recall from
a
Sect.
12.2.4
that a property of LLL reduction is that for 1
≤
j
≤
,
u
(
0
)
j
2
/
2
L
(
0
)
a
2
/
2
N
≤
λ
j
(
)
≤
.
