Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Low-latency digit-serial dual basis multiplier for lightweight cryptosystems

  • Author(s): Che Wun Chiou 1 1 ; Chiou-Yng Lee 2 2 ; Jim-Min Lin 3 3 ; Yun-Chi Yeh 4 4 ; Jeng-Shyang Pan 5 5
    • View affiliations
    • Affiliations: 1: Department of Computer Science and Information Engineering, Chien Hsin University of Science and Technology, Jhung-Li 320, Taiwan ;
      2: Department of Computer Information and Network Engineering, Lunghwa University of Science and Technology, Taoyuan County 333, Taiwan ;
      3: Department of Information Engineering and Computer Science, Feng Chia University, Taichung City 407, Taiwan ;
      4: Department of Electronic Engineering, Chien Hsin University of Science and Technology, Jhung-Li 320, Taiwan ;
      5: Fujian Provincial Key Laboratory of Big Data Mining and Applications, Fujian University of Technology, People's Republic of China
  • Source: Volume 11, Issue 6, November 2017, p. 301 – 311
    DOI:  10.1049/iet-ifs.2015.0336 , Print ISSN 1751-8709, Online ISSN 1751-8717
© The Institution of Engineering and Technology
Received 10/08/2015, Accepted 06/03/2017, Revised 06/05/2016, Published 16/03/2017

Various cryptosystems, such as elliptic curve and pairing-based cryptosystems, in resource-constrained security applications rely on finite field multiplication. For applications such as these, a digit-serial multiplier has the potential features to achieve a trade-off between space and time complexities. The authors propose an efficient decomposition of the multiplication into four independent sub-multiplication units to facilitate parallel processing, which is additionally facilitated by the systolic structures of the sub-multiplication units. The proposed architecture uses a four-bit scheme to construct a novel processing element, instead of using only one bit as is currently used in similar multipliers. The results of the synthesis show that the proposed digit-serial dual basis multiplier eliminates up to 96% of the critical path delay.

Inspec keywords: resource allocation; cryptography; parallel processing; computational complexity

Other keywords: systolic structures; critical path delay; finite field multiplication; submultiplication units; resource-constrained security applications; time complexity; space complexity; low-latency digit-serial dual basis multiplier; four-bit scheme; cryptosystems; parallel processing

Subjects: Computational complexity; Multiprocessing systems; Data security

References

    1. 1)
      • 35. Chiou, C.W., Chang, H.W., Liang, W.-Y., et al: ‘Low-complexity Gaussian normal basis multiplier over GF(2m)’, IET Inf. Sec., 2012, 6, (4), pp. 310–317.
    2. 2)
      • 11. Mastrovito, E.D.: ‘VLSI architectures for multiplication over finite field GF(2m)’. Proc. Sixth Int'l Conf. on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, (AAECC-6), Rome, 1988, pp. 297–309.
    3. 3)
      • 29. Agnew, G.B., Mullin, R.C., Onyszchuk, I.M., et al: ‘An implementation for a fast public-key cryptosystem’, J. Cryptol., 1991, 3, pp. 63–79.
    4. 4)
      • 16. Wu, H.: ‘Bit-parallel finite field multiplier and squarer using polynomial basis’, IEEE Trans. Comput., 2002, 51, (7), pp. 750–758.
    5. 5)
      • 18. Guo, J.-H., Wang, C.-L.: ‘Digit-serial systolic multiplier for finite fields GF(2m)’, IEE Proc. Comput. Digit.Tech., 1998, 145, (2), pp. 143–148.
    6. 6)
      • 22. Huang, W.-T., Chang, C.H., Chiou, C.W., et al: ‘Non-XOR approach for low-cost bit-parallel polynomial basis multiplier over GF(2m)’, IET Inf. Sec., 2011, 5, (3), pp. 152–162.
    7. 7)
      • 25. Lee, C.Y., Chiou, C.W.: ‘Efficient design of low-complexity bit-parallel systolic Hankel multipliers to implement multiplication in normal and dual bases of GF(2m)’, IEICE Trans. Fund. Electron. Commun. Comput. Sci., 2005, E88-A, (11), pp. 3169–3179.
    8. 8)
      • 13. Itoh, T., Tsujii, S.: ‘Structure of parallel multipliers for a class of fields GF(2m)’, Inf. Comput., 1989, 83, pp. 21–40.
    9. 9)
      • 1. Rivest, R.L., Shamir, A., Adleman, L.: ‘A method for obtaining digital signatures and public-key cryptosystems’, Commun. ACM, 1978, 21, pp. 120–126.
    10. 10)
      • 30. Hasan, M.A., Wang, M.Z., Bhargava, V.K.: ‘A modified Massey-Omura parallel multiplier for a class of finite fields’, IEEE Trans. Comput., 1993, 42, (10), pp. 1278–1280.
    11. 11)
      • 14. Lee, C.Y., Lu, E.H., Lee, J.Y.: ‘Bit-parallel systolic multipliers for GF(2m) fields defined by all-one and equally-spaced polynomials’, IEEE Trans. Comput., 2001, 50, (5), pp. 385–393.
    12. 12)
      • 15. Paar, C., Fleischmann, P., Roelse, P.: ‘Efficient multiplier architectures for Galois Fields GF(24n)’, IEEE Trans. Comput., 1998, 47, (2), pp. 162–170.
    13. 13)
      • 26. Massey, J.L., Omura, J.K.: ‘Computational method and apparatus for finite field arithmetic’. U.S. Patent Number 4,587,627, May 1986.
    14. 14)
      • 51. NanGate Standard Cell Library. http://www.si2.org/openeda.si2.org/projects/nangatelib/, 2015/5/7.
    15. 15)
      • 8. Koblitz, N.: ‘A family of Jacobians suitable for discrete log cryptosystems’. Advances in Cryptology, Proc. Crypto'88, 1988, pp. 94–99.
    16. 16)
      • 38. Fenn, S.T.J., Benaissa, M., Taylor, D.: ‘GF(2m) multiplication and division over the dual basis’, IEEE Trans. Comput., 1996, 45, (3), pp. 319–327.
    17. 17)
      • 5. IEEE Standard 1363-2000: ‘IEEE standard specifications for public-key cryptography’, January 2000.
    18. 18)
      • 46. Hua, Y.Y., Lin, J.-M., Chiou, C.W., et al: ‘Low space complexity digit serial dual basis systolic multiplier over Galois field GF(2m) using Hankel Matrix and Karatsuba algorithm’, IET Inf. Sec., 2013, 7, (2), pp. 75–86.
    19. 19)
      • 21. Talapatra, S., Rahaman, H., Mathew, J.: ‘Low complexity digit serial systolic Montgomery multipliers for special class of GF(2m)’, IEEE Trans. Very Large Scale Integr. Syst., 2010, 18, (5), pp. 847–852.
    20. 20)
      • 28. Reyhani-Masoleh, A.: ‘Efficient algorithms and architectures for field multiplication using Gaussian normal bases’, IEEE Trans. Comput., 2006, 55, (1), pp. 34–47.
    21. 21)
      • 33. Lee, C.-Y., Chiou, C.W.: ‘Scalable Gaussian normal basis multipliers over GF(2m) using Hankel matrix-vector representation’, J. Signal Process. Syst. Signal Image Video Technol., 2012, 69, (2), pp. 197–211.
    22. 22)
      • 7. ANSI X9.62-2005: ‘Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA)’ (American National Standards Institute (ANSI), 2005).
    23. 23)
      • 32. Fan, H., Hasan, M.A.: ‘Subquadratic computational complexity schemes for extended binary field multiplication using optimal normal bases’, IEEE Trans. Comput., 2007, 56, (10), pp. 1435–1437.
    24. 24)
      • 34. Chiou, C.W., Chuang, T.-P., Lin, S.-S., et al: ‘Palindromic-like representation for Gaussian normal basis multiplier over GF(2m) with odd type-t’, IET Inf. Sec., 2012, 6, (4), pp. 318–323.
    25. 25)
      • 41. Ibrahim, M.K., Aggoun, A.: ‘Dual basis digit serial GF(2m) multiplier’, Int. J. Electron., 2002, 89, (7), pp. 517–523.
    26. 26)
      • 24. Xie, J., He, J.J., Meher, P.K.: ‘Low latency systolic Montgomery multiplier for finite field GF(2m) based on pentanomials’, IEEE Trans. Very Large Scale Integr. Syst., 2013, 21, (2), pp. 385–389.
    27. 27)
      • 2. Miller, V.S.: ‘Use of elliptic curves in cryptography’. Proc. of Crypto 85, 1986 (LNCS, 218), pp. 417–426.
    28. 28)
      • 50. Pan, J.-S., Azarderakhsh, R., Kermani, M.M., et al: ‘Low-latency digit-serial systolic double basis multiplier over GF(2m) using subquadratic Toeplitz matrix-vector product approach’, IEEE Trans. Comput., 2014, 63, (5), pp. 1169–1181.
    29. 29)
      • 3. Koblitz, N.: ‘Elliptic curve cryptosystems’, Math. Comput., 1987, 48, pp. 203–209.
    30. 30)
      • 48. Pan, J.-S., Lee, C.-Y., Meher, P.K.: ‘Low-latency digit-serial and digit-parallel systolic multipliers for large binary extension fields’, IEEE Trans. Circ. Syst. I Reg. Papers, 2013, 60, (12), pp. 3195–3204.
    31. 31)
      • 45. Hua, Y.Y., Lin, J.-M., Chiou, C.W., et al: ‘A novel digit-serial dual basis Karatsuba multiplier over GF(2m)’, J. Comput., 2012, 23, (2), pp. 80–94.
    32. 32)
      • 19. Kim, C.H., Hong, C.P., Kwon, S.: ‘A digit-serial multiplier for finite field GF(2m)’, IEEE Trans. Very Large Scale Integr. Syst., 2005, 13, (4), pp. 476–483.
    33. 33)
      • 27. Wang, C.C., Troung, T.K., Shao, H.M., et al: ‘VLSI architectures for computing multiplications and inverses in GF(2m)’, IEEE Trans. Comput., 1985, C-34, (8), pp. 709–717.
    34. 34)
      • 37. Wu, H., Hasan, M.A., Blake, I.F.: ‘New low-complexity bit-parallel finite field multipliers using weakly dual bases’, IEEE Trans. Comput., 1998, 47, (11), pp. 1223–1234.
    35. 35)
      • 47. Imaña, J.L.: ‘Low latency GF(2m) polynomial basis multiplier’, IEEE Trans. Circ. Syst. I Reg. Papers, 2011, 58, (5), pp. 935–946.
    36. 36)
      • 36. Berlekamp, E.R.: ‘Bit-serial reed-solomon encoder’, IEEE Trans. Inf. Theory, 1982, IT-28, pp. 869–874.
    37. 37)
      • 9. Dutta, R., Barua, R., Sarkar, P.: ‘Pairing-based cryptographic protocols: a survey’. Cryptology ePrint Archive, Report 064/2004, 2004.
    38. 38)
      • 17. Fan, H., Hasan, M.A.: ‘A new approach to subquadratic space complexity parallel multipliers for extended binary fields’, IEEE Trans. Comput., 2007, 56, (2), pp. 224–233.
    39. 39)
      • 23. Xie, J., Meher, P.K., He, J.: ‘Low-latency area-delay-efficient systolic multiplier over GF(2m) for a wider class of trinomials using parallel register sharing’. IEEE Int. Symp. on Circuits and Systems, (ISCAS'12), Seoul, Korea, 2012, pp. 89–92.
    40. 40)
      • 49. Lin, W.-C., Ye, J.-H., Shieh, M.-D.: ‘Scalable Montgomery modular multiplication architecture with low-latency and low-memory bandwidth requirement’, IEEE Trans. Comput., 2014, 63, (2), pp. 475–483.
    41. 41)
      • 10. Bartee, T.C., Schneider, D.J.: ‘Computation with finite fields’, Information and Computing, 1963, 6, pp. 79–98.
    42. 42)
      • 39. Wang, M., Blake, I.F.: ‘Bit serial multiplication in finite fields’, SIAM J. Disc. Math., 1990, 3, (1), pp. 140–148.
    43. 43)
      • 42. Chang, P.-L., Chen, L.-H., Lee, C.-Y.: ‘Low-complexity dual basis digit serial GF(2m) multiplier’, ICIC Exp. Lett., 2009, 3, (4), pp. 1113–1118.
    44. 44)
      • 4. FIPS 186-2: ‘Digital signature standard (DSS)’ (Federal Information Processing Standards Publication 186-2, Nat'l Inst. of Standards and Technology, 2000).
    45. 45)
      • 40. Wang, J.-H., Chang, H.W., Chiou, C.W., et al: ‘Low-complexity design of bit-parallel dual basis multiplier over GF(2m)’, IET Inf. Sec., 2012, 6, (4), pp. 324–328.
    46. 46)
      • 44. Chen, L.-H., Chang, P.-L., Lee, C.-Y., et al: ‘Scalable and systolic dual basis multiplier over GF(2m)’, Int. J. Innovat. Comput. Inf. Control, 2011, 7, (3), pp. 1193–1208.
    47. 47)
      • 20. Kumar, S., Wollinger, T., Paar, C.: ‘Optimum digit-serial GF(2m) multipliers for curve-based cryptography’, IEEE Trans. Comput., 2006, 55, (10), pp. 1306–1311.
    48. 48)
      • 6. ISO/IEC 11770-3 : 2008: ‘Information technology – security techniques – key management – Part 3: mechanisms using asymmetric techniques’, 2008.
    49. 49)
      • 12. Koç, Ç.K., Sunar, B.: ‘Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields’, IEEE Trans. Comput., 1998, 47, (3), pp. 353–356.
    50. 50)
      • 43. Chang, P.-L., Hsieh, F.-H., Chen, L.-H., et al: ‘Efficient digit serial dual basis GF(2m) multiplier’. Proc. of the 2010 5th IEEE Conf. on Industrial Electronics and Applications, (ICIEA 2010), Taichung, Taiwan, 2010, pp. 166–170.
    51. 51)
      • 31. Kwon, S.: ‘A low complexity and a low latency bit parallel systolic multiplier over GF(2m) using an optimal normal basis of type II’. Proc. of the 16th IEEE Symp. on Computer Arithmetic, Santiago de Compostela, Spain, 2003, pp. 196–202.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0336
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0336
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address