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

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.

• Chiou-Yng Lee
• Wen-Yo Lee
• Chieh-Tsai Wu
• Cheng-Chen Yang

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

[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.