{"title":"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","volume":89,"journal":"International Journal of Computer and Information Engineering","pagesStart":811,"pagesEnd":818,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/9998321","abstract":"
Shifted polynomial basis (SPB) is a variation of
\r\npolynomial basis representation. SPB has potential for efficient
\r\nbit level and digi -level implementations of multiplication over
\r\nbinary extension fields with subquadratic space complexity. For
\r\nefficient implementation of pairing computation with large finite
\r\nfields, this paper presents a new SPB multiplication algorithm based
\r\non Karatsuba schemes, and used that to derive a novel scalable
\r\nmultiplier architecture. Analytical results show that the proposed
\r\nmultiplier provides a trade-off between space and time complexities.
\r\nOur proposed multiplier is modular, regular, and suitable for very
\r\nlarge scale integration (VLSI) implementations. It involves less
\r\narea complexity compared to the multipliers based on traditional
\r\ndecomposition methods. It is therefore, more suitable for efficient
\r\nhardware implementation of pairing based cryptography and elliptic
\r\ncurve cryptography (ECC) in constraint driven applications.<\/p>\r\n","references":"[1] W. Diffie and M. Hellman, \"New Directions in Cryptography,\u201d IEEE\r\nTrans. Information Theory, vol. 22, no. 6, pp. 644\u2013654, Nov. 1976.\r\n[2] \"Digital Signature Standard,\u201d National Institute of Standards and\r\nTechnology, 186-2, Jan. 2000.\r\n[3] N. Koblitz, \"Elliptic Curve Cryptosystems,\u201d Mathematics of\r\nComputation, vol. 48, no. 177, pp. 203\u2013209, 1987.\r\n[4] A. Menezes, I. Blake, S. Gao, R. Mullin, S. Vanstone, and\r\nT. Yaghoobian, Applications of Finite Fields. Kluwer Academic\r\nPublisher, 1993.\r\n[5] D. Boneh and M. K. Franklin, \"Identity-based encryption from the weil\r\npairing,\u201d SIAM Journal on Computing, vol. 32, no. 3, pp. 586\u2013615, 2003.\r\n[6] H. Fan and M. Hasan, \"Fast Bit Parallel Shifted Polynomial Basis\r\nMultipliers in GF(2n),\u201d IEEE Trans. Circuits and Systems I: Regular\r\nPapers, vol. 53, no. 12, pp. 2606\u20132615, 2006.\r\n[7] N. Mentens, S. B. Ors, B. Preneel, and J. Vandewalle, \"An FPGA\r\nImplementation of a Montgomery multiplier over GF(2m),\u201d in Proc.\r\nof the 7th IEEE Workshop on Design and Diagnostics of Electronic\r\nCircuits and Systems (DDECS), 2004, pp. 121\u2013128.\r\n[8] D. Kammler, D. Zhang, P. Schwabe, H. Scharwaechter, M. Langenberg,\r\nD. Auras, G. Ascheid, and R. Mathar, \"Designing an asip for\r\ncryptographic pairings over barreto-naehrig curves,\u201d in Cryptographic\r\nHardware and Embedded Systems - CHES 2009, ser. Lecture Notes in\r\nComputer Science, vol. 5747. Springer, Heidelberg, 2009, pp. 254\u2013271.\r\n[9] P. K. Meher, \"Systolic and Super-Systolic Multipliers for Finite Field\r\nGF(2m) Based on Irreducible Trinomials,\u201d IEEE Trans. Circuits and\r\nSystems I: Regular Papers, vol. 55, no. 4, pp. 1031\u20131040, May 2008.\r\n[10] C.-Y. Lee, E. H. Lu, and J. Y. Lee, \"Bit-Parallel Systolic Multipliers for\r\nGF(2m) Fields Defined by All-One and Equally Spaced Polynomials,\u201d\r\nIEEE Trans. Computers, vol. 50, no. 5, pp. 385\u2013393, May 2001.\r\n[11] G. N. Selimis, A. P. Fournaris, H. E. Michail, and O. Koufopavlou,\r\n\"Improved Throughput Bit-Serial Multiplier for GF(2m) Fields,\u201d\r\nIntegration, the VLSI journal, vol. 42, pp. 217\u2013226, 2009.\r\n[12] S. Fenn, M. Gossel, M. Benaissa, and D. Taylor, \"On-Line Error\r\nDetection for Bit-Serial Multipliers in GF(2m),\u201d Journal of Electronic\r\nTesting: Theory and Applications, vol. 13, no. 1, pp. 29\u201340, 1998.\r\n[13] S. Talapatra, H. Rahaman, and J. Mathew, \"Low complexity Digit Serial\r\nSystolic Montgomery Multipliers for Special Class of GF(2m),\u201d IEEE\r\nTrans. Very Large Scale Integration (VLSI) Systems, vol. 18, no. 5, pp.\r\n487\u2013852, May 2010.\r\n[14] M. Morales-Sandoval, C. Feregrino-Uribe, and P. Kitsos, \"Bit-serial\r\nand digit-serial GF(2m) Montgomery multipliers using linear feedback\r\nshift registers,\u201d IET Computers and Digital Techniques, vol. 5, no. 2, pp.\r\n86\u201394, 2011.\r\n[15] C.-Y. Lee and C. Chiou, \"Scalable Gaussian Normal Basis Multipliers\r\nover GF(2m) Using Hankel Matrix-Vector Representation,\u201d Journal of\r\nSignal Processing Systems, vol. 69, no. 2, pp. 197\u2013211, 2012.\r\n[16] A. Karatsuba and Y. Ofman, \"Multiplication of Multidigit Numbers on\r\nAutomata,\u201d ISoviet Physics-Doklady (English translation), vol. 7, no. 7,\r\npp. 595\u2013596, 1963.\r\n[17] C. Paar, \"A new architecture for a parallel finite field multiplier with low\r\ncomplexity based on composite fields,\u201d IEEE Trans. Computers, vol. 45,\r\nno. 7, pp. 856\u2013861, Jul. 1996.\r\n[18] A. Reyhani-Masoleh and M. Hasan, \"Low Complexity Bit Parallel\r\nArchitectures for Polynomial Basis Multiplication over GF(2m),\u201d IEEE\r\nTrans. Computers, vol. 53, no. 8, pp. 945\u2013959, 2004.\r\n[19] L. H. Chen, P. L. Chang, C.-Y. Lee, and Y. K. Yang, \"Scalable and\r\nSystolic Dual Basis Multiplier over GF(2m),\u201d Intl Journal of Innovative\r\nComputing, Information and Control, vol. 7, no. 3, pp. 1193\u20131208, Mar.\r\n2011.\r\n[20] C.-Y. Lee, C. W. Chiou, J. M. Lin, and C. C. Chang, \"Scalable\r\nand Systolic Montgomery Multiplier over GF(2m) Generated by\r\nTrinomials,\u201d IET Circuits, Devices & Systems, vol. 1, no. 6, pp. 477\u2013484,\r\n2007.\r\n[21] \"Nangate standard cell library,\u201d http:\/\/www.si2.org\/openeda.si2.org\/\r\nprojects\/nangatelib\/.\r\n[22] C.-Y. Lee, \"Super Digit-Serial Systolic Multiplier Over GF(2m),\u201d in\r\nSixth International Conference on Genetic and Evolutionary Computing,\r\n2012.\r\n[23] S. Talapatra, H. Rahaman, and S. K. Saha, \"Unified Digit Serial\r\nSystolic Montgomery Multiplication Architecture for Special Classes of\r\nPolynomials over GF(2m),\u201d in 13th Euromicro Conference on Digital\r\nSystem Design: Architectures, Methods and Tools, 2010.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 89, 2014"}