Cryptography Reference
In-Depth Information
quantum computation. They are based on the diculty of the problem of solving
multivariate quadratic equations over finite fields, which is in general NP-hard.
The focus of this paper is to further speed up hardware implementation of
Rainbow signature generation (without consideration of the area cost). The Oil-
Vinegar family of Multivariate Public Key Cryptosystems consists of three fam-
ilies: balanced Oil-Vinegar, unbalanced Oil-Vinegar and Rainbow [3], a multi-
layer construction using unbalanced Oil-Vinegar at each layer. There have been
some previous works to eciently implement multivariate signature schemes, e.g.
TTS on a low-cost smart card [4], minimized multivariate PKC on low-resource
embedded systems [5], some instances of MPKCs [6], SSE implementation of
multivariate PKCs on modern x86 CPUs [7]. Currently the best hardware im-
plementations of Rainbow signature are:
1. A parallel hardware implementation of Rainbow signature scheme [8], the
fastest work (not best in area utilization), which takes 804 clock cycles to gen-
erate a Rainbow signature;
2. A hardware implementation of multivariate signatures using systolic arrays
[9], which optimizes in terms of certain trade-off between speed and area.
In generation of Rainbow signature, the major computation components are: 1.
Multiplication of elements in finite fields; 2. Multiplicative inversion of elements
in finite fields; 3. Solving system of linear equations over finite fields. Therefore,
we focus on further improvement in these three directions.
Our contributions. In terms of multiplication over finite fields, we improve
the multiplication according to the design in [10]. In terms of solving system of
linear equations, our improvements are based on a parallel Gaussian elimination
over GF (2) [11], a systolic Gaussian elimination for computing multiplicative
inversion [12], and a systolic Gauss-Jordan elimination over GF (2 n ) [13], and
develop a new parallel hardware design for the Gauss-Jordan elimination to
solve a 12
×
12 system of linear equations with only 12 clock cycles. In terms of
multiplicative inversion, we design a novel partial multiplicative inverter based
on Fermat's theorem.
Through further other minor optimizations of the parallelization process and
by integrating the major optimizations above, we build a new hardware imple-
mentation, which takes only 198 clock cycles to generate a Rainbow signature,
a new record in generating digital signatures and four times faster than the
804-clock-cycle Balasubramanian-Bogdanov-Carter-Ding-Rupp design [8] with
similar parameters.
We test and verify our design on a Field-Programmable Gate Array (FPGA),
the experimental results confirm our estimates.
The rest of this paper is organized as follows: in Section 2, we present the
background information used in this paper; in Section 3, the proposed hardware
design for Rainbow signature scheme is presented; in Section 4, we implement
our design in a low-cost FPGA and experimental results are presented; in Section
5, the implementation is evaluated and compared with other hardware imple-
mentations; in Section 6, conclusions are summarized.
 
Search WWH ::




Custom Search