Scalable Systolic Multiplier over Binary Extension Fields Based on Two-Level Karatsuba Decomposition

Authors: Chiou-Yng Lee, Wen-Yo Lee, Chieh-Tsai Wu, Cheng-Chen Yang

Abstract:

Shifted polynomial basis (SPB) is a variation of polynomial basis representation. SPB has potential for efficient bit level and digi -level implementations of multiplication over binary extension fields with subquadratic space complexity. For efficient implementation of pairing computation with large finite fields, this paper presents a new SPB multiplication algorithm based on Karatsuba schemes, and used that to derive a novel scalable multiplier architecture. Analytical results show that the proposed multiplier provides a trade-off between space and time complexities. Our proposed multiplier is modular, regular, and suitable for very large scale integration (VLSI) implementations. It involves less area complexity compared to the multipliers based on traditional decomposition methods. It is therefore, more suitable for efficient hardware implementation of pairing based cryptography and elliptic curve cryptography (ECC) in constraint driven applications.

Keywords: Digit-serial systolic multiplier, elliptic curve cryptography (ECC), Karatsuba algorithm (KA), shifted polynomial basis (SPB), pairing computation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1092822

References:

[1] W. Diffie and M. Hellman, "New Directions in Cryptography,” IEEE Trans. Information Theory, vol. 22, no. 6, pp. 644–654, Nov. 1976.
[2] "Digital Signature Standard,” National Institute of Standards and Technology, 186-2, Jan. 2000.
[3] N. Koblitz, "Elliptic Curve Cryptosystems,” Mathematics of Computation, vol. 48, no. 177, pp. 203–209, 1987.
[4] A. Menezes, I. Blake, S. Gao, R. Mullin, S. Vanstone, and T. Yaghoobian, Applications of Finite Fields. Kluwer Academic Publisher, 1993.
[5] D. Boneh and M. K. Franklin, "Identity-based encryption from the weil pairing,” SIAM Journal on Computing, vol. 32, no. 3, pp. 586–615, 2003.
[6] H. Fan and M. Hasan, "Fast Bit Parallel Shifted Polynomial Basis Multipliers in GF(2n),” IEEE Trans. Circuits and Systems I: Regular Papers, vol. 53, no. 12, pp. 2606–2615, 2006.
[7] N. Mentens, S. B. Ors, B. Preneel, and J. Vandewalle, "An FPGA Implementation of a Montgomery multiplier over GF(2m),” in Proc. of the 7th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems (DDECS), 2004, pp. 121–128.
[8] D. Kammler, D. Zhang, P. Schwabe, H. Scharwaechter, M. Langenberg, D. Auras, G. Ascheid, and R. Mathar, "Designing an asip for cryptographic pairings over barreto-naehrig curves,” in Cryptographic Hardware and Embedded Systems - CHES 2009, ser. Lecture Notes in Computer Science, vol. 5747. Springer, Heidelberg, 2009, pp. 254–271.
[9] P. K. Meher, "Systolic and Super-Systolic Multipliers for Finite Field GF(2m) Based on Irreducible Trinomials,” IEEE Trans. Circuits and Systems I: Regular Papers, vol. 55, no. 4, pp. 1031–1040, May 2008.
[10] C.-Y. Lee, E. H. Lu, and J. Y. Lee, "Bit-Parallel Systolic Multipliers for GF(2m) Fields Defined by All-One and Equally Spaced Polynomials,” IEEE Trans. Computers, vol. 50, no. 5, pp. 385–393, May 2001.
[11] G. N. Selimis, A. P. Fournaris, H. E. Michail, and O. Koufopavlou, "Improved Throughput Bit-Serial Multiplier for GF(2m) Fields,” Integration, the VLSI journal, vol. 42, pp. 217–226, 2009.
[12] S. Fenn, M. Gossel, M. Benaissa, and D. Taylor, "On-Line Error Detection for Bit-Serial Multipliers in GF(2m),” Journal of Electronic Testing: Theory and Applications, vol. 13, no. 1, pp. 29–40, 1998.
[13] S. Talapatra, H. Rahaman, and J. Mathew, "Low complexity Digit Serial Systolic Montgomery Multipliers for Special Class of GF(2m),” IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol. 18, no. 5, pp. 487–852, May 2010.
[14] M. Morales-Sandoval, C. Feregrino-Uribe, and P. Kitsos, "Bit-serial and digit-serial GF(2m) Montgomery multipliers using linear feedback shift registers,” IET Computers and Digital Techniques, vol. 5, no. 2, pp. 86–94, 2011.
[15] C.-Y. Lee and C. Chiou, "Scalable Gaussian Normal Basis Multipliers over GF(2m) Using Hankel Matrix-Vector Representation,” Journal of Signal Processing Systems, vol. 69, no. 2, pp. 197–211, 2012.
[16] A. Karatsuba and Y. Ofman, "Multiplication of Multidigit Numbers on Automata,” ISoviet Physics-Doklady (English translation), vol. 7, no. 7, pp. 595–596, 1963.
[17] C. Paar, "A new architecture for a parallel finite field multiplier with low complexity based on composite fields,” IEEE Trans. Computers, vol. 45, no. 7, pp. 856–861, Jul. 1996.
[18] A. Reyhani-Masoleh and M. Hasan, "Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication over GF(2m),” IEEE Trans. Computers, vol. 53, no. 8, pp. 945–959, 2004.
[19] L. H. Chen, P. L. Chang, C.-Y. Lee, and Y. K. Yang, "Scalable and Systolic Dual Basis Multiplier over GF(2m),” Intl Journal of Innovative Computing, Information and Control, vol. 7, no. 3, pp. 1193–1208, Mar. 2011.
[20] C.-Y. Lee, C. W. Chiou, J. M. Lin, and C. C. Chang, "Scalable and Systolic Montgomery Multiplier over GF(2m) Generated by Trinomials,” IET Circuits, Devices & Systems, vol. 1, no. 6, pp. 477–484, 2007.
[21] "Nangate standard cell library,” http://www.si2.org/openeda.si2.org/ projects/nangatelib/.
[22] C.-Y. Lee, "Super Digit-Serial Systolic Multiplier Over GF(2m),” in Sixth International Conference on Genetic and Evolutionary Computing, 2012.
[23] S. Talapatra, H. Rahaman, and S. K. Saha, "Unified Digit Serial Systolic Montgomery Multiplication Architecture for Special Classes of Polynomials over GF(2m),” in 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, 2010.