access icon free Gaussian normal basis multiplier over GF(2 m ) using hybrid subquadratic-and-quadratic TMVP approach for elliptic curve cryptography

© The Institution of Engineering and Technology
Received 13/01/2017, Accepted 19/05/2017, Revised 18/04/2017, Published 26/09/2017

In recent years, subquadratric-and-quadratric Toeplitz matrix–vector product (TMVP) computations are widely used for the implementation of binary field multiplication in elliptic curve cryptography. Pure subquadratric TMVP structure involves significantly less space complexity and long computational delay, while quadratric TMVP structure involves larger space complexity and less computation delay. To optimise the tradeoff between time and space complexities, this study presents a novel hybrid multiplier for Gaussian normal basis (GNB) in GF(2 m ) which combines subquadratic and quadratic structures. From the theoretical analysis, it is shown that the proposed hybrid multiplier can save ∼18% space complexity and 12% time complexity than the existing GNB multiplier with pure TMVP decomposition.

Inspec keywords: Toeplitz matrices; computational complexity; public key cryptography

Other keywords: hybrid multiplier; theoretical analysis; time complexity; Toeplitz matrix-vector product; hybrid subquadratic-and-quadratic TMVP approach; binary field multiplication; GNB multiplier; computational delay; Gaussian normal basis multiplier; elliptic curve cryptography; space complexity; TMVP decomposition

Subjects: Cryptography; Data security; Algebra; Algebra

References

    1. 1)
      • 21. 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.
    2. 2)
      • 16. Berlekamp, E.R.: ‘Bit-serial Reed-Solomon encoder’, IEEE Trans. Inf. Theory, 1982, IT-28, pp. 869–874.
    3. 3)
      • 14. Lee, C.-Y., Meher, P.K., Lee, W.-Y.: ‘Subquadratic space complexity digit-serial multiplier over binary extension fields using Toom-Cook algorithm’. Proc. of 2014 Int. Symp. on Integrated Circuits (ISIC), Singapore, 10–12 December 2014, pp. 176–179.
    4. 4)
      • 31. Leone, M.: ‘A new low complexity parallel multiplier for a class of finite fields’. Proc. of Workshop Cryptographic Hardware and Embedded Systems (CHES 2001), Paris, France, 13–16 May 2001 (LNCS, 2162), pp. 160–170.
    5. 5)
      • 28. 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.
    6. 6)
      • 22. Reyhani-Masoleh, A.: ‘Efficient algorithms and architectures for field multiplication using Gaussian normal bases’, IEEE Trans. Comput., 2006, 55, (1), pp. 34–47.
    7. 7)
      • 37. Hasan, M.A., Negre, C.: ‘Subquadratic space complexity multiplier for a class of binary fields using Toeplitz matrix approach’. Proc. of 2009 19th IEEE Int. Symp. on Computer Arithmetic, Portland, Oregon, USA, 8–10 June 2009, pp. 67–75.
    8. 8)
      • 2. Peterson, W.W., Weldon, E.J.Jr.: ‘Error-correcting codes’ (Cambridge, MA: MIT Press, 1972).
    9. 9)
      • 4. Miller, V.S.: ‘Use of elliptic curves in cryptography’. Proc. of Crypto 85, 1986 (LNCS, 218), pp. 417–426.
    10. 10)
      • 34. Yang, C.-S., Pan, J.-S., Lee, C.-Y.: ‘Digit-serial GNB multiplier based on TMVP approach over GF(2m)’. Proc. of 2013 Second Int. Conf. on Robot, Vision and Signal Processing, Kitakyushu, Japan, 10–12 December 2013, pp. 123–128.
    11. 11)
      • 18. 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.
    12. 12)
      • 11. Itoh, T., Tsujii, S.: ‘Structure of parallel multipliers for a class of fields GF(2m)’, Inf. Comput., 1989, 83, pp. 21–40.
    13. 13)
      • 27. 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.
    14. 14)
      • 3. Federal Information Processing Standards Publication 197: ‘Announcing the advanced encryption standard (AES)’, United States National Institute of Standards and Technology (NIST). November 26, 2001.
    15. 15)
      • 8. ANSI X9.62-2005: ‘Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA)’, American National Standards Institute (ANSI), November2005.
    16. 16)
      • 29. Chiou, C.W., Chang, C.-C., Lee, C.-Y., et al: ‘Concurrent error detection and correction in Gaussian normal basis multiplier over GF(2m)’, IEEE Trans. Comput., 2009, 58, (6), pp. 851–857.
    17. 17)
      • 5. Koblitz, N.: ‘Elliptic curve cryptosystems’, Math. Comput., 1987, 48, pp. 203–209.
    18. 18)
      • 36. Ibrahim, A., Gebali, F., Al-Somani, T.: ‘Systolic array architectures for Sunar-Koc optimal normal basis type II multiplier’, IEEE Trans. Very Large Scale Integr., 2015, 23, (10), pp. 2090–2102.
    19. 19)
      • 24. 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.
    20. 20)
      • 9. Bartee, T.C., Schneider, D.J.: ‘Computation with finite fields’, Inf. Comput., 1963, 6, pp. 79–98.
    21. 21)
      • 33. Park, S.-M., Hong, D., Seo, C.: ‘Subquadratic space complexity multiplier for GF(2n) using type 4 Gaussian normal bases’, ETRI J., 2013, 35, (3), pp. 523–529.
    22. 22)
      • 19. 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.
    23. 23)
      • 35. Gebali, F., Al-Somani, T.: ‘Finite field multiplication using reordered normal basis multiplier’. Sixth Int. Conf. on Broadband and Wireless Computing Communication and Applications (BWCCA), Barcelona, Spain, 26–28 October 2011, pp. 320–326.
    24. 24)
      • 23. 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.
    25. 25)
      • 12. 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.
    26. 26)
      • 6. Koblitz, N., Menezes, A.: ‘Pairing-based cryptography at high security levels’. IMA ’05 Proceedings of the 10th International conference on Cryptography and Coding, 2005 (LNCS, 3796), pp. 13–36.
    27. 27)
      • 25. 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, 15–18 June 2003, pp. 196–202.
    28. 28)
      • 20. Massey, J.L., Omura, J.K.: ‘Computational method and apparatus for finite field arithmetic’. U.S. Patent Number 4,587,627, May 1986.
    29. 29)
      • 13. Paar, C.: ‘A new architecture for a parallel finite field multiplier with low complexity based on composite fields’, IEEE Trans. Comput., 1996, 45, (7), pp. 856–861.
    30. 30)
      • 17. 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.
    31. 31)
      • 38. Hasan, M.A., Méloni, N., Namin, A.H., et al: ‘Block recombination approach for subquadratic space complexity binary field multiplication based on Toeplitz matrix-vector product’, IEEE Trans. Comput., 2012, 61, (2), pp. 151–158.
    32. 32)
      • 15. 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.
    33. 33)
      • 26. 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.
    34. 34)
      • 10. Mastrovito, E.D.: ‘VLSI architectures for multiplication over finite field GF(2m)’. Proc. Sixth Int. Conf. Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, AAECC-6, Rome, July 1988, pp. 297–309.
    35. 35)
      • 30. Ash, D.W., Blake, I.F., Vanstone, S.A.: ‘Low complexity normal bases’, Discrete Appl. Math., 1989, 25, pp. 191–210.
    36. 36)
      • 39. NanGate Standard Cell Library. Available at http://www.si2.org/openeda.si2.org/projects/nangatelib/.
    37. 37)
      • 7. IEEE Standard 1363-2000: ‘IEEE standard specifications for public-key cryptography’, January2000.
    38. 38)
      • 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.
    39. 39)
      • 1. Blahut, R.E.: ‘Fast algorithms for digital signal processing’ (Reading, MA: Addison-Wesley, 1984).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2017.0015
Loading

Related content

content/journals/10.1049/iet-cds.2017.0015
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading