Cryptography Reference
In-Depth Information
6 Conclusions
We propose a new optimized hardware implementation of Rainbow signature
scheme, which can generate a Rainbow signature with only 198 clock cycles, a
new record in generating digital signatures.
Our main contributions include three parts. 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 finite fields. Third, we design
a novel partial multiplicative inverter to speed up the multiplicative inversion
of finite field elements. Through further other minor optimizations of the paral-
lelization 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, four times faster than the 804-clock-cycle Balasubramanian-
Bogdanov-Carter-Ding-Rupp design [8] with similar parameters. Our implemen-
tation focuses solely on speeding up the signing process not area utilization.
The optimization method of three-operand multiplier, partial multiplicative
inverter, and LSEs solver proposed can be further applied to various applications
like matrix factorization, matrix inversion, and other multivariate PKCs.
×
Acknowledgement.
This work is supported by National Natural Science Foun-
dation of China under Grant No. 61170080 and 60973131, and supported by
GuangdongProvinceUniversities and Colleges PearlRiver ScholarFunded Scheme
(2011). This paper is also supported by the Fundamental Research Funds for the
Central Universities of China under Grant No.2009ZZ0035 and No.2011ZG0015.
References
1. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete loga-
rithms on a quantum computer. SIAM Review 41(2), 303-332 (1999)
2. Ding, J., Schmidt, D.: Multivariate public key cryptosystems. In: Advances in
Information Security, vol. 25, Springer, Heidelberg (2006)
3. Ding, J., Schmidt, D.: Rainbow, a New Multivariable Polynomial Signature
Scheme. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS,
vol. 3531, pp. 164-175. Springer, Heidelberg (2005)
4. Yang, B.-Y., Chen, J.-M., Chen, Y.-H.: TTS: High-Speed Signatures on a Low-Cost
Smart Card. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156,
pp. 371-385. Springer, Heidelberg (2004)
5. Yang, B.-Y., Cheng, C.-M., Chen, B.-R., Chen, J.-M.: Implementing Minimized
Multivariate PKC on Low-Resource Embedded Systems. In: Clark, J.A., Paige,
R.F., Polack, F.A.C., Brooke, P.J. (eds.) SPC 2006. LNCS, vol. 3934, pp. 73-88.
Springer, Heidelberg (2006)
6. Chen, A.I.-T., Chen, C.-H.O., Chen, M.-S., Cheng, C.-M., Yang, B.-Y.: Practical-
Sized Instances of Multivariate PKCs: Rainbow, TTS, and
IC-derivatives. In:
Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 95-108.
Springer, Heidelberg (2008)
