Cryptography Reference
In-Depth Information
•
Arithmetic formulation of the next-state logic using Lagrange interpolation.
•
Randomized embedding to solve the nonuniformity problem discussed before.
In this method, each state value will have multiple images and this will provide
unpredictability and uniformity.
More specifically, we first propose making state transitions work according to an
arithmetic formula in a nonredundant field GF(
q
), i.e.
s
where
s
is the
next-state value,
i
is the input, and
s
is the current-state value. In this setting,
s
,
s
,
and
i
=
f
(
s
,
i
)
.
However, this is not sufficient for solving the previously discussed nonuniformity
problem because even though the state transitions are now working according to an
arithmetic formula, the same nonuniform behavior is observed at the state registers.
To solve this problem, we need unpredictability. In other words, the state machine
variables must be practically unpredictable to the attacker. As a result, as the second
step of the solution, we propose embedding the nonredundant field
GF
∈
GF
(
q
)
(
q
)
into
a larger redundant ring
R = Z
M
using a transformation
φ
:
GF
(
q
)
→ R
(or
φ
: R → R
is a homomorphism. Therefore, all the arithmetic operations
defined for GF(
q
) can also be carried out in
) where
φ
R
. In our case, randomized embedding
is achieved by defining the ring modulus
M
and the scaling factor
S
with
M
=
S
×
q
where
q
is the prime defining the field GF(
q
). In this setting, we define the function
φ
as
φ(
s
)
=
s
+
R
×
q
(
mod
M
)
where
R
is a randomly chosen value from
Z
S
.This
scaling effectively partitions the ring
into co-sets, of which only one contains the
nonredundant codewords. As a result of this scaling, each state and input value now
has
S
images. In other words, the same state and input will now be represented by
S
different values in the ring
R
depending on the value of the random
R
. This will
increase the uniformity of the state values observed at the output of the next-state
logic, and essentially increase the error detection capability of the nonlinear coding
technique we propose in this section. Note that when the state value is reduced using
q
, we obtain the nonredundant value of the state. Note that the state and input values
observed in this FSM will randomly be one of the
S
images of their nonredundant
values. A numerical application of this protection scheme is shown in Example
11.4. Note that in this example
q
R
11. This means that the nonredundant value of
each state and input value will be one of
=
(i.e. integers
modulo 11). This is the only co-set that includes the nonredundant state and input
values. However, due to the randomization process, each nonredundant state and
input value will have
S
{
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
10
}
24, and so on).
We now formally define a randomized robust code by merging this embedding
with the robust code definition introduced by Gaubatz et al. [156] in Definition 11.6
as follows.
=
390451572 different images (2
≡
13
≡
Definition 11.7
[10] We define the co-set randomized robust code
(
n
,
k
)
with
r
=
n
−
k
redundant bits as
C
={
(
x
,
w
)
|
x
=
y
+
R
×
q
(
mod
M
),
∀
x
and
∀
y
∈ Z
M
,
w
=
x
2
(
mod
p
)
∈
GF
(
p
),
R
∈ Z
S
}
where
r
=
k
,
k
≥
max
(
log
2
M
,
log
2
p
)
.
After the randomization of the next-state function
f
is achieved, we can use indi-
vidually robust arithmetic circuits such as multipliers, adders, and so on to build the
