access icon free Subquadratic space complexity Gaussian normal basis multipliers over GF(2 m ) based on Dickson–Karatsuba decomposition

Gaussian normal basis (GNB) of the even-type is popularly used in elliptic curve cryptosystems. Efficient GNB multipliers could be realised by Toeplitz matrix-vector decomposition to realise subquadratic space complexity architectures. In this study, Dickson polynomial representation is proposed as an alternative way to represent an GNB of characteristic two. The authors have derived a novel recursive Dickson–Karatsuba decomposition to achieve a subquadratic space-complexity parallel GNB multiplier. By theoretical analysis, it is shown that the proposed subquadratic multiplier saves about 50% bit-multiplications compared with the corresponding subquadratic GNB multiplication using Toeplitz matrix-vector product approach.

Inspec keywords: vectors; Gaussian processes; computational complexity; public key cryptography; matrix decomposition; Toeplitz matrices; recursive estimation

Other keywords: recursive Dickson-Karatsuba decomposition; subquadratic space complexity architectures; parallel GNB multiplier; even-type; bit-multiplications; elliptic curve cryptosystems; Dickson polynomial representation; Gaussian normal basis multipliers; Toeplitz matrix-vector decomposition

Subjects: Cryptography theory; Other topics in statistics; Algebra; Cryptography; Other topics in statistics; Algebra; Computational complexity

References

    1. 1)
    2. 2)
    3. 3)
      • 8. Lee, C.-Y.: ‘Concurrent error detection architectures for Gaussian normal basis multiplication over GF(2m)’, Integration, 2010, 43, (1), pp. 113123.
    4. 4)
      • 23. Lidl, R., Mullen, G., Turnwald, G.: ‘Dickson polynomials, vol. 65 of Longman Scientific & Technical, Harlow, Pitman Monogr. Surv. Pure Appl. Math., 1993.
    5. 5)
    6. 6)
    7. 7)
      • 15. Weimerskirch, A., Paar, C.: ‘Generalizations of the Karatsuba Algorithm for Efficient Implementations’. Technical Report, University of Ruhr, Bochum, Germany, 2003.
    8. 8)
    9. 9)
      • 1. Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA), American National Standards Institute Std. ANSI X. 9.62, 1999.
    10. 10)
      • 12. Lidl, R., Niederreiter, H.: ‘Introduction to finite fields and their applications’ (Cambridge University Press, 1997, 2nd edn.).
    11. 11)
    12. 12)
      • 14. Karatsuba, A., Ofman, Y.: ‘Multiplication of multidigit numbers on automata’, ISoviet Physics-Doklady (English translation), 1993, 7, (7), pp. 595596.
    13. 13)
    14. 14)
      • 24. Massey, J., Omura, J.: ‘Computational method and apparatus for finite arithmetic’, 1986.
    15. 15)
    16. 16)
      • 2. Digital Signature Standard (DSS), Federal Information Processing Standards Publication 186-2, National Institute of Standards and Technology Std.2000.
    17. 17)
    18. 18)
    19. 19)
    20. 20)
    21. 21)
    22. 22)
    23. 23)
    24. 24)
      • 21. Ozbudak, F., Akleylek, S., Cenk, M.: ‘A new representation of elements of binary fields with sub-quadratic space complexity multiplication of polynomials’, IEICE Trans., 2013, 96-A, (10), pp. 20162024.
    25. 25)
    26. 26)
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2014.0276
Loading

Related content

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