Cryptography Reference
In-Depth Information
The fault detection in the AND and XOR blocks of the bit-serial and bit-parallel
PB multipliers can be implemented using Properties 10.3 and 10.4, respectively.
Now, the main remaining block in these multipliers is the
x
module. The following
lemma can be presented to implement the fault detection circuit in this module [356].
=
m
−
1
i
=
n
−
1
i
a
i
x
i
be the input of the x module
and its encoding, respectively. The encoded output of the x module, i.e.,
a
i
x
i
A
Lemma 10.6
Let A
and
ˆ
=
0
=
0
A
, can be
obtained as follows:
A
=
A
a
n
−
1
F
x
+ˆ
(
x
),
F
where A
=
A
·
xmodF
(
x
)
and
(
x
)
is the encoding of F
(
x
)
[356].
Lemma 10.6 and Properties 10.3 and 10.4 are enough to implement the fault
detection circuit for the bit-serial and bit-parallel PB multipliers using linear codes.
10.3 Time Redundancy-Based Fault Detection
The second common approach for fault detection in finite field arithmetic operations
is based on time redundancy and has been used in many works such as [28, 87, 86, 248,
249]. This approach is efficient for pipelined multipliers, including systolic and semi-
systolic array multipliers. The time redundancy-based approach takes advantage of
some well-known techniques such as recomputing with shifted operands (RESO)
[320, 321] or alternate-data retry [375]. In this section, we describe some of the
existing works for fault detection in finite field arithmetic using time redundancy.
In [249], an RESO-based approach has been proposed for fault detection in a
semi-systolic implementation of the PB multiplication. In this approach first the
multiplication is performed using the main inputs
A
2
m
,
B
∈
GF
(
)
, which results
in
C
=
A
·
B
mod
F
(
x
)
. In the second round,
A
and
B
are represented using the
x
2
x
m
−
1
x
m
basis
{
1
,
x
,
,...,
,
}
and the final result is converted to the main basis, i.e.,
x
2
x
m
−
1
{
, and compared with
C
.
Another time redundancy-based approach is proposed in [87] for semi-systolic
implementation of the Montgomery multiplication. The first set of the inputs used
in this approach comprises
A
and
B
1
,
x
,
,...,
}
2
m
∈
GF
(
)
and the multiplication result is
C
=
A
·
B
mod
F
(
x
)
. The second set of th
e
inputs comprise the Montgomery
A
x
m
x
m
residues, define
d a
s
=
A
·
mod
F
(
x
)
and
B
=
B
·
mod
F
(
x
)
. The output of
x
−
m
this operation is
C
=
A
·
B
·
mod
F
(
x
)
. After completi
ng
both multiplications,
x
m
one can compute
C
and compare it with
C
to detect the errors.
To increase the
fa
ult detection capability, the operation is repeated by shifting the
operands
A
and
A
as well.
The approach proposed in [87] has been modified in [177] to reduce the overhead.
The difference between [87] and [177] is that the latter uses a multiplication by
x
−
1
·
mod
F
(
x
)