Cryptography Reference
In-Depth Information
High-Speed Hardware Implementation of
Rainbow Signature on FPGAs
Shaohua Tang
1
,HaiboYi
1
, Jintai Ding
2
,
3
, Huan Chen
1
,andGuominChen
1
1
School of Computer Science & Engineering,
South China University of Technology, Guangzhou, China
shtang@IEEE.org,
{
haibo.yi87,sarlmolapple
}
@gmail.com, huangege@qq.com
2
Department of Applied Mathematics,
South China University of Technology, Guangzhou, China
3
Department of Mathematical Sciences,
University of Cincinnati, OH, USA
jintai.ding@mail.uc.edu
Abstract.
We propose a new ecient hardware implementation of Rain-
bow signature scheme. We enhance the implementation in three direc-
tions. First, we develop a new parallel hardware design for the Gauss-
Jordan elimination, and solve a 12
×
12 system of linear equations with
only 12 clock cycles. Second, a novel multiplier is designed to speed up
multiplication of three elements over a finite field. Third, we design a
novel partial multiplicative inverter to speed up the multiplicative inver-
sion of finite field elements. Through further other minor optimizations
of the parallelization process and by integrating the major optimizations
above, we build a new hardware implementation, which takes only 198
clock cycles to generate a Rainbow signature, a new record in gener-
ating digital signatures and four times faster than the 804-clock-cycle
Balasubramanian-Bogdanov-Carter-Ding-Rupp design with similar pa-
rameters.
Keywords:
Multivariate Public Key Cryptosystems (MPKCs), digital
signature, Rainbow, finite field, Field-Programmable Gate Array (FPGA),
Gauss-Jordan elimination, multiplication of three elements.
1
Introduction
Due to the fast growth of broad application of cryptography, the use of secure and
ecient hardware architectures for implementations of cryptosystems receives
considerable attention. In terms of asymmetric cryptosystems, most schemes
currently used are based on the hardness of factoring large numbers or discrete
logarithm problems. However, a potential powerful quantum computer could
put much of currently used public key cryptosystems in jeopardy due to the
algorithm by Peter Shor [1].
Multivariate Public Key Cryptosystems (MPKCs) [2] is one of main families
of public key cryptosytsems that have the potential to resist the attacks by
