A PARALLEL HARDWARE ARCHITECTURE FOR FAST SIGNATURE GENERATION OF RAINBOW
This thesis deals with the conceptualization, design and implementation of an area-time efficient architecture for the multivariate quadratic signature scheme, Rainbow. Multivariate Public Key Cryptosystem(MPKC) schemes are in general much more computationally efficient than number theoretic-based schemes. This has led to many new constructions and Rainbow is one of them. It belongs to the class of mixed schemes under Multivariate Quadratic (MQ) constructions . The software implementation of Rainbow has been submitted to ECRYPT Benchmarking of Assymetric Systems (eBATS) . We investigate the requirements of implementing Rainbow in hardware and demonstrate its efficiency when compared to other schemes. As a result of the investigation, one of the important contributions of this thesis is the design and implementation of hardware-optimized, highly parallelized Gaussian elimination architecture, named G-SMITH (Extended- Scalable Matrix Inversion and Triangularization Hardware) . This architecture is adapted for Rainbow, nevertheless it can be used by virtually any multivariate scheme, which needs to solve linear system of equations over GF(2^l) in its central mapping function. Rainbow also involves affine linear transformations as a part of the signature generation procedure, for which we have re-used the G-SMITH hardware itself, thereby saving on area. As a result, the proposed Rainbow datapath architecture requires an area of 63,593 gate equivalents and computes the signature in 804 clock cycles. The area-time requirements of Rainbow, thus demonstrate that mixed MQ schemes offer massive parallelism and have the capability of generating signatures much faster than the legacy schemes such as RSA and ECDSA.
School:University of Cincinnati
School Location:USA - Ohio
Source Type:Master's Thesis
Keywords:multivariate signature schemes special purpose hardware rainbow g smith
Date of Publication:01/01/2007