http://iet.metastore.ingenta.com
1887

Low-latency digit-serial dual basis multiplier for lightweight cryptosystems

Low-latency digit-serial dual basis multiplier for lightweight cryptosystems

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

References

    1. 1)
      • 1. Rivest, R.L., Shamir, A., Adleman, L.: ‘A method for obtaining digital signatures and public-key cryptosystems’, Commun. ACM, 1978, 21, pp. 120126.
    2. 2)
      • 2. Miller, V.S.: ‘Use of elliptic curves in cryptography’. Proc. of Crypto 85, 1986 (LNCS, 218), pp. 417426.
    3. 3)
      • 3. Koblitz, N.: ‘Elliptic curve cryptosystems’, Math. Comput., 1987, 48, pp. 203209.
    4. 4)
      • 4. FIPS 186-2: ‘Digital signature standard (DSS)’ (Federal Information Processing Standards Publication 186-2, Nat'l Inst. of Standards and Technology, 2000).
    5. 5)
      • 5. IEEE Standard 1363-2000: ‘IEEE standard specifications for public-key cryptography’, January 2000.
    6. 6)
      • 6. ISO/IEC 11770-3 : 2008: ‘Information technology – security techniques – key management – Part 3: mechanisms using asymmetric techniques’, 2008.
    7. 7)
      • 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).
    8. 8)
      • 8. Koblitz, N.: ‘A family of Jacobians suitable for discrete log cryptosystems’. Advances in Cryptology, Proc. Crypto'88, 1988, pp. 9499.
    9. 9)
      • 9. Dutta, R., Barua, R., Sarkar, P.: ‘Pairing-based cryptographic protocols: a survey’. Cryptology ePrint Archive, Report 064/2004, 2004.
    10. 10)
      • 10. Bartee, T.C., Schneider, D.J.: ‘Computation with finite fields’, Information and Computing, 1963, 6, pp. 7998.
    11. 11)
      • 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. 297309.
    12. 12)
      • 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. 353356.
    13. 13)
      • 13. Itoh, T., Tsujii, S.: ‘Structure of parallel multipliers for a class of fields GF(2m)’, Inf. Comput., 1989, 83, pp. 2140.
    14. 14)
      • 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. 385393.
    15. 15)
      • 15. Paar, C., Fleischmann, P., Roelse, P.: ‘Efficient multiplier architectures for Galois Fields GF(24n)’, IEEE Trans. Comput., 1998, 47, (2), pp. 162170.
    16. 16)
      • 16. Wu, H.: ‘Bit-parallel finite field multiplier and squarer using polynomial basis’, IEEE Trans. Comput., 2002, 51, (7), pp. 750758.
    17. 17)
      • 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. 224233.
    18. 18)
      • 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. 143148.
    19. 19)
      • 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. 476483.
    20. 20)
      • 20. Kumar, S., Wollinger, T., Paar, C.: ‘Optimum digit-serial GF(2m) multipliers for curve-based cryptography’, IEEE Trans. Comput., 2006, 55, (10), pp. 13061311.
    21. 21)
      • 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. 847852.
    22. 22)
      • 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. 152162.
    23. 23)
      • 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. 8992.
    24. 24)
      • 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. 385389.
    25. 25)
      • 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. 31693179.
    26. 26)
      • 26. Massey, J.L., Omura, J.K.: ‘Computational method and apparatus for finite field arithmetic’. U.S. Patent Number 4,587,627, May 1986.
    27. 27)
      • 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. 709717.
    28. 28)
      • 28. Reyhani-Masoleh, A.: ‘Efficient algorithms and architectures for field multiplication using Gaussian normal bases’, IEEE Trans. Comput., 2006, 55, (1), pp. 3447.
    29. 29)
      • 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. 6379.
    30. 30)
      • 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. 12781280.
    31. 31)
      • 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. 196202.
    32. 32)
      • 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. 14351437.
    33. 33)
      • 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. 197211.
    34. 34)
      • 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. 318323.
    35. 35)
      • 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. 310317.
    36. 36)
      • 36. Berlekamp, E.R.: ‘Bit-serial reed-solomon encoder’, IEEE Trans. Inf. Theory, 1982, IT-28, pp. 869874.
    37. 37)
      • 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. 12231234.
    38. 38)
      • 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. 319327.
    39. 39)
      • 39. Wang, M., Blake, I.F.: ‘Bit serial multiplication in finite fields’, SIAM J. Disc. Math., 1990, 3, (1), pp. 140148.
    40. 40)
      • 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. 324328.
    41. 41)
      • 41. Ibrahim, M.K., Aggoun, A.: ‘Dual basis digit serial GF(2m) multiplier’, Int. J. Electron., 2002, 89, (7), pp. 517523.
    42. 42)
      • 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. 11131118.
    43. 43)
      • 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. 166170.
    44. 44)
      • 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. 11931208.
    45. 45)
      • 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. 8094.
    46. 46)
      • 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. 7586.
    47. 47)
      • 47. Imaña, J.L.: ‘Low latency GF(2m) polynomial basis multiplier’, IEEE Trans. Circ. Syst. I Reg. Papers, 2011, 58, (5), pp. 935946.
    48. 48)
      • 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. 31953204.
    49. 49)
      • 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. 475483.
    50. 50)
      • 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. 11691181.
    51. 51)
      • 51. NanGate Standard Cell Library. http://www.si2.org/openeda.si2.org/projects/nangatelib/, 2015/5/7.
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
This is a required field
Please enter a valid email address