Cryptography Reference
In-Depth Information
proposed robust FSM. To achieve this, we utilize the nonlinear code explained in
Definition 11.7 to encode the state variables and inputs. Next, we use the individually
robust arithmetic circuits that will work in the ring
to implement the next-state
function
f
. Robust adder and multiplier implementation examples that work under
the utilized code are provided in [156].
In the following theorem, we establish the error detection probability of our
scheme. A detailed proof of this theorem can be found in [10].
R
Theorem 11.4
[10] For the nonlinear code C that is defined as in Definition 11.8,
the error masking probability will be upper-bounded by S
−
1
2
k
·
max
(
4
,
−
p
+
1
)
,
2
k
where S
>
max
(
4
,
−
p
+
1
)
.
Example 11.4
Consider the FSM of Fig.
11.10
. As discussed before, this FSM
bounces between the “Square” and “Multiply” states most of the time. If we select
GF
(
q
)
=
GF
(
11
)
and
S
=
390451572, then
M
=
4294967292 and we will need a
(
64
,
32
)
-code with
p
=
4294967291. In this case, injected errors are detected with a
S
−
1
2
k
2
32
probability of at least 1
−
·
max
(
4
,
−
p
+
1
)
=
1
−
(
−
4294967291
+
1
)/(
2
×
2
−
27
. The denominator in this case becomes 2
390451572
S
because the
“Square” and “Multiply” states and their images will be uniformly distributed.
)
1
−
×
11.7.2 Case Study
In this section, we present the application of the proposed technique to the example
FSM shown in Fig.
11.10
. The first step is to use two-level Lagrange interpolation
to generate an algebraic polynomial for the next state logic. This polynomial rep-
resents the next-state
s
as a function of the input and current state variables
i
and
s
, respectively. For the example FSM we investigate here, the following polyno-
mial (see [10] for more details on the computation process) shows the result of the
two-level Lagrange interpolation:
s
=
s
6
s
5
f
(
s
,
i
)
=
(
4
i
)
+
(
2
+
4
i
)
s
4
s
3
s
2
+
(
+
)
+
(
+
)
+
(
+
)
+
(
+
)
+
.
3
6
i
1
2
i
5
3
i
5
i
s
i
(11.7)
This function can be implemented in an efficient way. The idea is to add time-
redundancy and reuse the expensive hardware modules (e.g. the multiplier and the
adder) in a serial manner. This can be achieved by rearranging the next-state polyno-
mial of (
11.7
) using Horner's method. In this case, the next-state equation becomes
s
=
((((((
4
i
)
s
+
(
2
+
4
i
))
s
+
(
3
+
6
i
))
s
+
(
1
+
2
i
))
s
+
(
5
+
3
i
))
s
+
(
5
+
i
))
s
+
i
.
(11.8)
Once this polynomial is computed, the next step is to encode the input and current
state values using the co-set randomized code of Definition 11.7. In this case, the
input will be
i
2
s
2
(
i
,
|
|
p
)
and the current state will be
(
s
,
|
|
p
)
where
i
,
s
∈
Z
M
.Next,
