Cryptography Reference
In-Depth Information
4
3
Polynomial
Evaluation
Solving System of
Linear Equations
5
2
6
Affine
Transformation
Messages
1
Signatures
7
Fig. 1.
The Flowchart to Generate Rainbow Signature
3.2 Choice of Irreducible Polynomial for the Finite Field
The choice of the irreducible polynomial for the finite field
k
is a critical part
of our hardware design, since it affects the eciency of the operations over the
finite field. The irreducible polynomials for
GF
(2
8
)over
GF
(2) can be expressed
as 9-bit binary digits with the form
x
8
+
x
k
+
...
+1,where0
<k<
8andthefirst
bit and the last bit are valued one. There are totally 16 candidates. We evaluate
the performance of the multiplications based on these irreducible polynomials
respectively.
By comparing the eciency of signature generations basing on different irre-
ducible polynomials,
x
8
+
x
6
+
x
3
+
x
2
+ 1 is finally chosen as the irreducible
polynomial in our hardware design.
3.3 Ecient Design of Multiplication of Three Elements
In Rainbow signature generation, we notice that there exist not only multipli-
cation of two elements but also multiplication of three elements. An optimized
design of the multiplier can dramatically improve the overall hardware execution
eciency.
Therefore, we design new implementation to speed up multiplication of three
elements based on the multiplication of two elements [10]. The new design is
based on a new observation that, in multiplication of three elements over
GF
(2
8
),
it is much faster to multiply everything first than perform modular operation
than the other way around. This is quite anti-intuitive and it works only over
small fields. This idea, in general, is not applicable for large fields.
7
7
7
a
i
x
i
,
b
(
x
)=
b
i
x
i
and
c
(
x
)=
c
i
x
i
are three elements
Suppose
a
(
x
)=
i
=0
i
=0
i
=0
in
GF
(2
8
)=
GF
(2)[
x
]
/f
(
x
),and
7
d
i
x
i
d
(
x
)=
a
(
x
)
× b
(
x
)
× c
(
x
)(mod(
f
(
x
))) =
(2)
i
=0
is the expected multiplication result, where
f
(
x
) is the irreducible polynomial.
