Cryptography Reference
In-Depth Information
First, we compute
v
ij
for
i
=0
,
1
, ...,
21 and
j
=0
,
1
, ...,
7accordingto
x
i
mod
f
(
x
)=
j
=0
v
ij
x
j
. Next, we compute
S
i
for
i
=0
,
1
, ...,
21 via
S
i
=
7
a
j
b
k
c
l
.
j
+
k
+
l
=
i
21
After that, we compute
d
i
for
i
=0
,
1
, ...,
7via
d
i
=
=0
v
ji
S
j
. Finally, the
j
7
=0
d
i
x
i
.
multiplication result of
a
(
x
)
× b
(
x
)
× c
(
x
)
mod f
(
x
)is
i
3.4 Ecient Design of Partial Multiplicative Inversion
The multiplicative inverse over finite fields is a crucial but time-consuming op-
eration in multivariate signature. An optimized design of the inverter can really
help to improve the overall performance. Since multiplicative inversion is only
used in solving system of linear equations, we do not implement a fully multi-
plicative inverter but adopt a partial inverter based on Fermat's theorem in our
design.
Suppose
f
(
x
) is the irreducible polynomial and
β
is an element over
GF
(2
8
),
where
β
=
β
7
x
7
+
β
6
x
6
+
β
5
x
5
+
β
4
x
4
+
β
3
x
3
+
β
2
x
2
+
β
1
x
+
β
0
.
According
to the Fermat's theorem, we have
β
2
8
=
β
,and
β
−
1
=
β
2
8
−
2
=
β
254
.
Since
2
8
2=2+2
2
+2
3
+2
4
+2
5
+2
6
+2
7
,then
β
−
1
=
β
2
β
4
β
8
β
16
β
32
β
64
β
128
.
We can then construct the logic expressions of these items.
−
β
2
i
=
β
7
x
2
i
×
7
+
β
6
x
2
i
×
6
+
β
5
x
2
i
×
5
+
β
4
x
2
i
×
4
+
β
3
x
2
i
×
3
+
β
2
x
2
i
×
2
+
β
1
x
2
i
+
β
0
,
(3)
The computation of
x
2
i
×j
should be reduction modulo the irreducible polyno-
mial, where
i
=1
,
2
, ...,
7and
j
=0
,
1
, ...,
7, then
β
2
i
is transformed into the
equivalent form. For instance,
β
2
i
=
β
7
x
7
+
β
6
x
6
+
β
5
x
5
+
β
4
x
4
+
β
3
x
3
+
β
2
x
2
+
β
1
x
+
β
0
.
We adopt the three-input multiplier described in Section 3.3 to design the
partial inverter, where
ThreeMult
(
v
1
,v
2
,v
3) stands for multiplication of three
elements and
v
1,
v
2,
v
3 are operands and
S
1
,
S
2
are the multiplication results.
S
1
=
ThreeMult
(
β
2
,β
4
,β
8
)
,
S
2
=
ThreeMult
(
β
16
,β
32
,β
64
)
.
(4)
Wecallthetriple(
S
1
,S
2
,β
128
) the partial multiplicative inversion of
β
.Belowwe
will present how we adopt partial inversion in solving system of linear equations.
3.5 Optimized Gauss-Jordan Elimination
We propose a parallel variant of Gauss-Jordan elimination for solving a system
of linear equations with the matrix size 12
12. The optimization and paral-
lelization of Gauss-Jordan elimination can enhance the overall performance of
solving system of linear equations.
×
