[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Faster characteristic three polynomial multiplication and its application to NTRU Prime decapsulation

  • Regular Paper
  • Published:
Journal of Cryptographic Engineering Aims and scope Submit manuscript

Abstract

Efficient computation of polynomial multiplication over characteristic three fields is required for post-quantum cryptographic applications which gain importance upon the recent advances in quantum computers. In this paper, we propose three new polynomial multiplication algorithms over \({\mathbb {F}}_{3}\) and show that they are more efficient than the current state-of-the-art algorithms. We first examine through the well-known multiplication algorithms in \({\mathbb {F}}_{3}{[}x{]}\) including the Karatsuba 2-way and 3-way split formulas along with the latest enhancements. Then, we propose a new 4-way split polynomial multiplication algorithm and an improved version of it which are both derived by using interpolation in \({\mathbb {F}}_{9}\), the finite field with nine elements. Moreover, we propose a 5-way split multiplication algorithm and then compare the efficiencies of these algorithms altogether. Even though there exist 4-way or 5-way split multiplication algorithms in characteristic two (binary) fields, there has not been any such algorithms developed for characteristic three fields before this paper. We apply the proposed algorithms to the NTRU Prime protocol, a post-quantum key encapsulation mechanism, submitted to the NIST PQC Competition by Bernstein et al., performing polynomial multiplication over characteristic three fields in its decapsulation phase. We observe that the new hybrid algorithms provide a \(12.9\%\) reduction in the arithmetic complexity. Furthermore, we implement these new hybrid methods on Intel (R) Core (TM) i7-9750H architecture using C and obtain a \(37.3\%\) reduction in the implementation cycle count.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Adrian, D., Bhargavan, K., Durumeric, Z., Gaudry, P., Green, M., Halderman, J.A., Heninger, N., Springall, D., Thomé, E., Valenta, L., VanderSloot, B., Wustrow, E., Zanella-Béguelin, S., Zimmermann, P.: Imperfect forward secrecy: how diffie-hellman fails in practice. In: Association for Computing Machinery, pp. 5–17 (2015)

  2. U. S. National Security Agency. Commercial National Security Algorithm Suite and Quantum Computing Faq. https://cryptome.org/2016/01/CNSA-Suite-and-Quantum-Computing-FAQ.pdf (2016)

  3. Alagic, G., Alperin-Sheriff, J., Apon, D., Cooper, D., Dang, Q., Kelsey, J., Liu, Y., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Smith-Tonel, D.: Status Report on the Second Round of the Nist Post-Quantum Cryptography Standardization Process. https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf (2020)

  4. Bently, J.L., Haken, D., Saxe, J.B.: A general method for solving divide-and-conquer recurrences. ACM SIGACT News 12(3), 36–44 (1980)

    Article  Google Scholar 

  5. Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.: Ntru Prime. NIST Post-Quantum Cryptography Standardization Process-Round-1. https://ntruprime.cr.yp.to/nist/ntruprime-20171130.pdf (2017)

  6. Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.: NTRU Prime: reducing attack surface at low cost. In: International Conference on Selected Areas in Cryptography, 24, pp. 235–260 (2017)

  7. Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.: Ntru prime. NIST Post-Quantum Cryptography Standardization Process-Round-2. https://ntruprime.cr.yp.to/nist/ntruprime-20190330.pdf (2019)

  8. Bernstein, D.J.: Batch binary edwards. In: Advances in Cryptology - CRYPTO 2009, vol. 5677 of LNCS, pp. 317–336 (2009)

  9. Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E., Zimmermann, P.: https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html (2019)

  10. Cenk, M.: Karatsuba-like formulae and their associated techniques. J. Cryptogr. Eng. 8(3), 259–269 (2018)

    Article  Google Scholar 

  11. Cenk, M., Hasan, M.A.: Some new results on binary polynomial multiplication. J. Cryptogr. Eng. 5(4), 289–303 (2015)

    Article  Google Scholar 

  12. Cenk, M., Koç, Ç.K., Özbudak, F.: Polynomial multiplication over finite fields using field extensions and interpolation. In: IEEE Symposium on Computer Arithmetic, pp. 84–91 (2009)

  13. Cenk, M., Negre, C., Hasan, M.A.: Improved three-way split formulas for binary polynomial multiplication. In: Selected Areas in Cryptography, pp. 384–398 (2011)

  14. Cenk, M., Negre, C., Hasan, M.A.: Improved 3-way split formulas for binary polynomial and toeplitz matrix vector products. IEEE Trans. Comput. 62, 1345–1361 (2013)

    Article  MathSciNet  Google Scholar 

  15. Cenk, M., Ozbudak, F.: Efficient multiplication in \({ F}_{3^{lm}}\), \(m\ge 1\) and \(5\le l \le 18\). In: AFRICACRYPT, pp. 406–414 (2008)

  16. Cenk, M., Zadeh, F.H., Hasan, M.A.: New efficient algorithms for multiplication over fields of characteristic three. J. Sign. Process Syst. 90(3), 285–294 (2018)

    Article  Google Scholar 

  17. NSA Suite B Cryptography. Suit b implementers’ guide to Nist sp 800-56a. https://web.archive.org/web/20160306033416/http://www.nsa.gov/ia/_files/SuiteB_Implementer_G-113808.pdf (2009)

  18. Diffie, W., Hellman, M.: New directions in cryptography. IEEE Trans. Inf. Theor. 22(6), 644–654 (1976)

    Article  MathSciNet  Google Scholar 

  19. Fan, H., Hasan, M.A.: A new approach to subquadratic space complexity parallel multipliers for extended binary fields. IEEE Trans. Comput. 56, 224–233 (2007)

    Article  MathSciNet  Google Scholar 

  20. Grover, Lov K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pp. 212–219 (1996)

  21. Ilter, M.B., Cenk, M.: Efficient big integer multiplication in cryptography. Int. J. Inf. Secur. Sci. 6(4), 70–78 (2017)

    Google Scholar 

  22. Martinis, J., Boixo, S.: Quantum supremacy using a programmable superconducting processor. https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html (2019)

  23. Merkle, R.C.: Secure communications over insecure channels. Assoc. Comput. Mach. 21(4), 294–299 (1978)

    MATH  Google Scholar 

  24. Montgomery, P.L.: Five, six and seven-term karatsuba-like formulae. IEEE Trans. Comput. 54, 362–369 (2005)

    Article  Google Scholar 

  25. NIST. Recommendation for pair-wise key establishment schemes using discrete logarithm cryptography. https://csrc.nist.gov/publications/detail/sp/800-56a/revised/archive/2007-03-14 (2006)

  26. Oneill, M., Rafferty, C.: Evaluation of large integer multiplication methods on hardware. IEEE Trans. Comput. 66, 1369–1382 (2017)

    Article  MathSciNet  Google Scholar 

  27. Pednault, E., Gunnels, J., Maslov, D., Gambetta, J.: On quantum supremacy. In: IBM Research Blog (2019)

  28. Certicom Research. Standards for efficient cryptography, sec 1: Elliptic curve cryptography, version 2.0. https://www.secg.org/sec1-v2.pdf (2009)

  29. Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Assoc. Comput. Mach. 21(2), 120–126 (1978)

    MathSciNet  MATH  Google Scholar 

  30. Rosen, K.H.: Elementary Number Theory and Its Application, 6th edn. Addison-Wesley (2011)

  31. Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)

    Article  MathSciNet  Google Scholar 

  32. Shor, P.W.: Refined analysis and improvements on some factoring algorithms. J. Algorithms 3(2), 101–127 (1982)

    Article  MathSciNet  Google Scholar 

  33. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134, (1994)

  34. Weimerskirch, A., Paar, C.: Generalizations of the Karatsuba Algorithm for Efficient Implementations. IACR Cryptol. ePrint Arch., (2006)

  35. Winograd, S.: Arithmetic complexity of computations. In: Society For Industrial & Applied Mathematics, U.S. (1980)

  36. Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press (2001)

  37. Zhou, Gang, Michalik, Harald: Comments on a new architecture for a parallel finite field multiplier with low complexity based on composite field. IEEE Trans. Comput. 59(7), 1007–1008 (2010)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. MEB, Ankara, Turkey

    Esra Yeniaras

  2. Middle East Technical University, Ankara, Turkey

    Murat Cenk

Authors
  1. Esra Yeniaras
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Murat Cenk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Esra Yeniaras.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yeniaras, E., Cenk, M. Faster characteristic three polynomial multiplication and its application to NTRU Prime decapsulation. J Cryptogr Eng 12, 329–348 (2022). https://doi.org/10.1007/s13389-021-00282-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13389-021-00282-7

Keywords

Search

Navigation