Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

An Efficient Noncommutative NTRU from Semidirect Product

  • Conference paper
  • First Online:

Abstract

NTRU is one of the most extensively studied lattice-based schemes. Its flexible design has inspired different proposals constructed over different rings, with some aiming to enhance security and others focusing on improving performance. The literature has introduced a line of noncommutative NTRU-like designs that claim to offer greater resistance to existing attacks. However, most of these proposals are either theoretical or fall short in terms of time and memory requirements when compared to standard NTRU. To our knowledge, DiTRU (Africacrypt 2024) is the first noncommutative analog of NTRU provided as a complete package. Although DiTRU is practical, it operates at two times slower than NTRU with no decryption failure. Additionally, key generation, encryption, and decryption are 1.2, 1.7, and 1.7 times slower, respectively, with negligible decryption failure. In this work, we introduce a noncommutative version of NTRU that offers comparable performance and key sizes to NTRU while improving upon DiTRU. Our cryptosystem is based on the GR-NTRU framework, utilizing the group ring of a semidirect product of cyclic groups over the ring of Eisenstein integers. This design allows for an efficient construction with key generation speeds approximately two (three) times faster than NTRU (DiTRU). Further, the proposed scheme provides roughly a speed-up by a factor of 1.2 (2) while encrypting/decrypting messages of the same length over NTRU (DiTRU). We provide a reference implementation in C for the proposed cryptosystem to prove our claims.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7550
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 9437
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Notes

  1. 1.

    The curve in Fig. 2 lies slightly below the experimental observations since\(\tilde{P}_{success}(N,q)\) (19) gives the underestimated value of the probability of successful decryption while the actual value of our model is given by\(P_{success}(N,q)\) (18).

  2. 2.

    For NTRU, the length of the key is assumed to be\(\sqrt{{4N'}/{3}+1}\) and the value of\(q'\) that achieves no decryption failure is\(q'\ge 16N'/3\). For our scheme, although the norm of the target vector has upper bound\(\sqrt{{320N}/{9}}\). However, it is empirically observed that the norm of the target vector is approximately\(\sqrt{{160N}/{9}}\). Therefore, for a conservative estimation of the lattice gap and the blocksize, we consider the latter value of the norm.

References

  1. Albrecht, M., Bai, S., Ducas, L.: A subfield lattice attack on overstretched NTRU assumptions. In: Advances in Cryptology – CRYPTO 2016, pp. 153–178. Springer Berlin Heidelberg (2016).https://doi.org/10.1007/978-3-662-53018-4_6

  2. Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key\(\{\)Exchange-A\(\}\) new hope. In: 25th USENIX Security Symposium (USENIX Security 16), pp. 327–343 (2016).https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_alkim.pdf

  3. Aono, Y., Wang, Y., Hayashi, T., Takagi, T.: Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 789–819. Springer (2016).https://doi.org/10.1007/978-3-662-49890-3_30

  4. Babai, L.: On lovász’ lattice reduction and the nearest lattice point problem. Combinatorica6, 1–13 (1986).https://doi.org/10.1007/BF02579403

    Article MathSciNet  Google Scholar 

  5. Bagheri, K., Sadeghi, M.R., Panario, D.: A non-commutative cryptosystem based on quaternion algebras. Des. Codes Crypt.86, 2345–2377 (2018).https://doi.org/10.1007/s10623-017-0451-4

  6. Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 10–24. SIAM (2016).https://doi.org/10.1137/1.9781611974331.ch2

  7. Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.: NTRU Prime: reducing attack surface at low cost. In: Selected Areas in Cryptography – SAC 2017, pp. 235–260. Springer International Publishing (2018).https://doi.org/10.1007/978-3-319-72565-9_12

  8. Bernstein, D.J., Yang, B.Y.: Fast constant-time GCD computation and modular inversion. IACR Trans. Crypt. Hardw. Embed. Syst.2019(3), 340–398 (2019).https://doi.org/10.13154/tches.v2019.i3.340-398

  9. Chen, C., et al.: PQC round-3 candidate: NTRU. technical report. Tech. rep., NTRU Cryptosystems Technical Report No.11, Version 2, March 2001. Report (2019).https://ntru.org/f/ntru-20190330.pdf

  10. Chen, C., Hoffstein, J., Whyte, W., Zhang, Z.: NIST PQ submission: NTRUEncrypt a lattice based encryption algorithm. NIST (2017).https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-1-submissions

  11. Chen, Y.: Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe. Ph. D. thesis, l’Université Paris Diderot (2013).http://www.theses.fr/2013PA077242

  12. Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 1–20. Springer (2011).https://doi.org/10.1007/978-3-642-25385-0_1

  13. Coppersmith, D., Shamir, A.: Lattice attacks on NTRU. In: Advances in Cryptology — EUROCRYPT ’97, pp. 52–61. Springer Berlin Heidelberg, Berlin, Heidelberg (1997).https://doi.org/10.1007/3-540-69053-0_5

  14. Ducas, L., van Woerden, W.: NTRU fatigue: how stretched is overstretched? In: Advances in Cryptology – ASIACRYPT 2021, pp. 3–32. Springer International Publishing (2021).https://doi.org/10.1007/978-3-030-92068-5_1

  15. Dummit, D.S., Foote, R.M.: Abstract Algebra, 3 edn. Wiley, Inc. (2003).https://www.wiley.com/en-in/Abstract+Algebra%2C+3rd+Edition-p-9780471433347

  16. Fox, N.: Spectra of semidirect products of cyclic groups. Rose-Hulman Undergraduate Math. J.11 (2010).https://scholar.rose-hulman.edu/rhumj/vol11/iss2/7

  17. Gentry, C.: Key recovery and message attacks on NTRU-composite. In: Pfitzmann, B. (ed.) Advances in Cryptology — EUROCRYPT 2001, pp. 182–194. Springer Berlin Heidelberg, Berlin, Heidelberg (2001).https://doi.org/10.1007/3-540-44987-6_12

  18. Hoffstein, J., Pipher, J., Silverman, J.: An Introduction to Mathematical Cryptography, 1st edn. Springer Publishing Company, Incorporated, NY (2008)

    Google Scholar 

  19. Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: International Algorithmic Number Theory Symposium, pp. 267–288. Springer, Berlin, Heidelberg (1998).https://doi.org/10.1007/BFb0054868

  20. Hoffstein, J., Silverman, J.H., Whyte, W.: Meet-in-the-middle attack on an NTRU private key. Tech. rep., Technical report, NTRU Cryptosystems, July 2006. Report (2006).https://ntru.org/f/tr/tr004v2.pdf

  21. Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Advances in Cryptology - CRYPTO 2007, pp. 150–169. Springer Berlin Heidelberg (2007).https://doi.org/10.1007/978-3-540-74143-5_9

  22. Howgrave-Graham, N., et al.: The impact of decryption failures on the security of NTRU encryption. In: Boneh, D. (ed.) Advances in Cryptology - CRYPTO 2003, pp. 226–246. Springer Berlin Heidelberg, Berlin, Heidelberg (2003).https://doi.org/10.1007/978-3-540-45146-4_14

  23. Howgrave-Graham, N., Silverman, J.H., Whyte, W.: Choosing parameter sets for NTRUEncrypt with NAEP and SVES-3. In: Menezes, A. (ed.) Topics in Cryptology – CT-RSA 2005, pp. 118–135 (2005).https://doi.org/10.1007/978-3-540-30574-3_10

  24. Hurley, T.: Group rings and rings of matrices. Int. J. Pure Appl. Math.31, 319–335 (2006).https://www.researchgate.net/publication/228928727_Group_rings_and_rings_of_matrices

  25. Hülsing, A., Rijneveld, J., Schanck, J., Schwabe, P.: High-speed key encapsulation from NTRU. In: International Conference on Cryptographic Hardware and Embedded Systems, CHES 2017, pp. 232–252 (2017).https://doi.org/10.1007/978-3-319-66787-4_12

  26. Jarvis, K., Nevins, M.: ETRU: NTRU over the eisenstein integers. Des. Codes Cryptogr.74, 219–242 (2015).https://doi.org/10.1007/s10623-013-9850-3

    Article MathSciNet  Google Scholar 

  27. Kim, J., Lee, C.: A polynomial time algorithm for breaking NTRU encryption with multiple keys. Des. Codes Crypt.91, 2779–2789 (2023).https://doi.org/10.1007/s10623-023-01233-5

    Article MathSciNet  Google Scholar 

  28. Kirchner, P., Fouque, P.A.: Revisiting lattice attacks on overstretched NTRU parameters. In: Advances in Cryptology – EUROCRYPT 2017, pp. 3–26. Springer International Publishing (2017).https://doi.org/10.1007/978-3-319-56620-7_1

  29. Kirshanova, E., May, A., Nowakowski, J.: New NTRU records with improved lattice bases. In: Post-Quantum Cryptography, pp. 167–195 (2023).https://doi.org/10.1007/978-3-031-40003-2_7

  30. Kumar, V., Raya, A., Gangopadhyay, S., Gangopadhyay, A.K.: Lattice attack on group ring NTRU: the case of the dihedral group.arXiv:2309.08304 (2023)

  31. Laarhoven, T.: Search problems in cryptography: from fingerprinting to lattice sieving. Ph. D. thesis, Eindhoven University of Technology (2015).https://research.tue.nl/en/publications/search-problems-in-cryptography-from-fingerprinting-to-lattice-si

  32. Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische annalen261(ARTICLE), 515–534 (1982).https://doi.org/10.1007/BF01457454

  33. Malekian, E., Zakerolhosseini, A.: OTRU: a non-associative and high speed public key cryptosystem. In: 2010 15th CSI International Symposium on Computer Architecture and Digital Systems, pp. 83–90 (2010).https://doi.org/10.1109/CADS.2010.5623536

  34. Malekian, E., Zakerolhosseini, A., Mashatan, A.: QTRU : a lattice attack resistant version of NTRU PKCS based on quaternion algebra. IACR Cryptol. ePrint Archive386 (2009).https://eprint.iacr.org/2009/386

  35. Raya, A., Kumar, V., Gangopadhyay, S.: DiTRU: a resurrection of NTRU over dihedral group. In: Vaudenay, S., Petit, C. (eds.) Progress in Cryptology - AFRICACRYPT 2024, pp. 349–375. Springer Nature Switzerland, Cham (2024).https://doi.org/10.1007/978-3-031-64381-1_16

  36. Schnorr, C.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci.53(2), 201–224 (1987).https://doi.org/10.1016/0304-3975(87)90064-8

    Article MathSciNet  Google Scholar 

  37. Silverman, J.H.: Almost inverses and fast NTRU key creation. NTRU Cryptosystems Technical Report #14 (1999).https://ntru.org/f/tr/tr014v1.pdf

  38. Stinson, D., Paterson, M.: Cryptography: Theory and Practice, 4 edn. CRC Press, Chapman and Hall Book, Taylor & Francis (2017).https://doi.org/10.1201/9781315282497

  39. Thakur, K.: A variant of NTRU with split quaternions algebra. Palestine J. Math.6(2), 598–610 (2017).https://pjm.ppu.edu/sites/default/files/papers/PJM_April_2017_28.pdf

  40. Truman, K.R.: Analysis and extension of non-commutative NTRU. Ph. D. dissertation, University of Maryland (2007).https://drum.lib.umd.edu/handle/1903/7344

  41. Venier, D., Cheung, R.C.: A highly parallel constant-time almost-inverse algorithm. In: 2020 IEEE International Conference on Signal Processing, Communications and Computing (ICSPCC), pp. 1–6 (2020).https://doi.org/10.1109/ICSPCC50002.2020.9259505

  42. Yasuda, T., Dahan, X., Sakurai, K.: Characterizing NTRU-variants using group ring and evaluating their lattice security. IACR Cryptol. ePrint Arch. 1170 (2015).http://eprint.iacr.org/2015/1170

Download references

Acknowledgment

The authors want to express their gratitude to the reviewers whose valuable suggestions have greatly helped improve the editorial quality of the paper. Vikas Kumar would like to thank CSIR for supporting his research through grant no. 09/143(1038)/2020-EMR-I.

Author information

Authors and Affiliations

  1. Department of Mathematics, Indian Institute of Technology Roorkee, Roorkee, 247667, India

    Vikas Kumar & Aditi Kar Gangopadhyay

  2. Department of Computer Science and Engineering, Indian Institute of Technology Roorkee, Roorkee, 247667, India

    Ali Raya & Sugata Gangopadhyay

  3. Department of Information Technology, Indian Institute of Engineering Science and Technology Shibpur, Howrah, 711103, India

    Md Tarique Hussain

Authors
  1. Vikas Kumar

    You can also search for this author inPubMed Google Scholar

  2. Ali Raya

    You can also search for this author inPubMed Google Scholar

  3. Aditi Kar Gangopadhyay

    You can also search for this author inPubMed Google Scholar

  4. Sugata Gangopadhyay

    You can also search for this author inPubMed Google Scholar

  5. Md Tarique Hussain

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toVikas Kumar.

Editor information

Editors and Affiliations

  1. Indian Institute of Technology, Kharagpur, West Bengal, India

    Sourav Mukhopadhyay

  2. Naval Postgraduate School, Monterey, CA, USA

    Pantelimon Stănică

Appendices

Sketched Design Rationale

We follow the same design framework as adopted in NTRUEncrypt [10] to construct a Probabilistic Public Key Encryption (PPKE) scheme. The proposal derives its CPA security from the NTRU assumption, which is transformed into CCA2 secure by employing the NAEP padding mechanism [23]. All the steps in Fig. 3 are almost identical to the design rationale used in NTRUEncrypt submission [10], except that the operations are now performed in the noncommutative structure\(R^{\omega }(C_N\rtimes C_3)\) moduloq orp.

Fig. 3.
figure 3

Sketch of the CCA2 secure PPKE for our proposal. The functionSampler randomly samples an element unique to the seed from the input space. The spaces\(L_f, L_g, L_{\phi }\), and\(L_m\) are defined in the Sect. 3.

Constant Time Inversion Algorithm for \({\mathbb Z}[\omega ]/\langle q\rangle C_N\)

figure c

Algorithm 3 is a direct adaptation of the Bernstein-Yang algorithm [8] with the required modifications to our new ring\({\mathbb Z}[\omega ]/\langle q\rangle C_N\).

  • Multiplication of two Eisenstein integers requires 3 integer multiplications.

  • Moduloq in\({\mathbb Z}\) (for a primeq) requires 4 scalar multiplications in constant-time, therefore moduloq in\({\mathbb Z}[\omega ]\) (for a prime\(q+0\omega \)) requires 8 scalar multiplications (Algorithm  refalg:division).

  • Inversion of an element in\({\mathbb Z}[\omega ]\) moduloq is upper bounded by\(17+10\log _2(q-2)\) scalar multiplications as in Lemma1.

Therefore, lines 10 and 11 contribute to\(14(N+1)\) scalar multiplications each. Line 13 contributes to\(17+10\log _2(q-2)\) multiplications, and line 14 contributes to 11N scalar multiplications.

Rights and permissions

Copyright information

© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kumar, V., Raya, A., Gangopadhyay, A.K., Gangopadhyay, S., Hussain, M.T. (2025). An Efficient Noncommutative NTRU from Semidirect Product. In: Mukhopadhyay, S., Stănică, P. (eds) Progress in Cryptology – INDOCRYPT 2024. INDOCRYPT 2024. Lecture Notes in Computer Science, vol 15495. Springer, Cham. https://doi.org/10.1007/978-3-031-80308-6_1

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7550
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 9437
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp