Rad HAZU, Matematičke znanosti, Vol. 25 (2021), 181-193.

CRYPTANALYSIS OF ITRU

Hayder R. Hashim, Alexandra Molnár and Szabolcs Tengely

Institute of Mathematics, University of Debrecen, P. O. Box 400, 4002 Debrecen, Hungary
Faculty of Computer Science and Mathematics, University of Kufa, P.O.Box 21, 54001 Al Najaf, Iraq
e-mail: hashim.hayder.raheem@science.unideb.hu
e-mail: hayderr.almuswi@uokufa.edu.iq

Institute of Mathematics, University of Debrecen, P. O. Box 400, 4002 Debrecen, Hungary
e-mail: alexandra980312@freemail.hu

Institute of Mathematics, University of Debrecen, P. O. Box 400, 4002 Debrecen, Hungary
e-mail: tengely@science.unideb.hu

Abstract.   ITRU cryptosystem is a public key cryptosystem and one of the known variants of NTRU cryptosystem. Instead of working in a truncated polynomial ring, ITRU cryptosystem is based on the ring of integers. The authors claimed that ITRU has better features comparing to the classical NTRU, such as having a simple parameter selection algorithm, invertibility, and successful message decryption, and better security. In this paper, we present an attack technique against the ITRU cryptosystem, and it is mainly based on a simple frequency analysis on the letters of ciphertexts.

2020 Mathematics Subject Classification.   94B40, 94A60, 68P25.

Key words and phrases.   NTRU, ITRU, public key cryptography, cryptanalysis.

Full text (PDF) (free access)

DOI: https://doi.org/10.21857/yrvgqtexl9

References:

  1. W. D. Banks and I. E. Shparlinski, A variant of NTRU with non-invertible polynomials, in: Progress in Cryptology - INDOCRYPT 2002, Lecture Notes in Comput. Sci. 2551, Springer, Berlin, pp. 62-70.
    CrossRef

  2. H. Beker and F. Piper, Cipher systems: The protection of communications, A New Electronics Communications International Book, Northwood Books, London, 1982.

  3. A. A. Bruen and M. A. Forcinito, Cryptography, information theory, and errorcorrection. A handbook for the 21st century, John Wiley & Sons, Hoboken, 2005.
    MathSciNet

  4. M. G. Camara, De. Sow and Dj. Sow, DTRU1: First generalization of NTRU using dual integers, International Journal of Algebra 12 (7) (2018), 257-271.
    CrossRef

  5. M. Coglianese and B. M. Goi, MaTRU: A new NTRU-based cryptosystem, in: Progress in Cryptology - INDOCRYPT 2005, Lecture Notes in Comput. Sci. 3797, Springer, Berlin, 2005. pp. 232-243.
    MathSciNet     CrossRef

  6. D. Coppersmith and A. Shamir, Lattice attacks on NTRU, in: Advances in Cryptology — EUROCRYPT '97, Lecture Notes in Comput. Sci. 1233, Springer, Berlin, 1997, pp. 52-61.
    MathSciNet     CrossRef

  7. T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory 31 (4) (1985), 469-472.
    MathSciNet     CrossRef

  8. W. F. Friedman, The index of coincidence and its applications in cryptography, Department of Ciphers. Publ 22. Riverbank Laboratories, Geneva, Illinois, 1922.

  9. W. F. Friedman, Codes And Ciphers (CRYPTOLOGY), Encyclopaedia Britannica, 1961, pp. 1-8.

  10. P. Gaborit, J. Ohler and P. Solé, CTRU, a polynomial analogue of NTRU, INRIA, 2002.

  11. J. N. Gaithuru, M. Salleh and I. Mohamad, ITRU: NTRU-based cryptosystem using ring of integers, International Journal of Innovative Computing 7 (1) (2017), 33-38.
    CrossRef

  12. C. Gentry, Key recovery and message attacks on NTRU-composite, in: Advances in Cryptology - EUROCRYPT 2001, Lecture Notes in Comput. Sci. 2045, Springer, Berlin, 2001, pp. 182-194.
    MathSciNet     CrossRef

  13. H. Gilbert, D. Gupta, A. Odlyzko and J. J. Quisquater, Attacks on Shamir's 'RSA for paranoids', Inf. Process. Lett. 68 (4) (1998), 197-199.
    CrossRef

  14. O. Goldreich, S. Goldwasser and S. Halevi, Public-key cryptosystems from lattice reduction problems, in: Advances in Cryptology - CRYPTO '97, Lecture Notes in Comput. Sci. 1294, Springer, Berlin, 1997, pp. 112-131.
    MathSciNet     CrossRef

  15. S. Gurpreet and K. Supriya, A study of encryption algorithms (RSA, DES, 3DES and AES) for information security, International Journal of Computer Applications 67 (19) (2013), 33-38.

  16. J. Hoffstein, J. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, in: Algorithmic number theory, ANTS-III, Lecture Notes in Comput. Sci. 1423, Springer, Berlin, 1998, pp. 267-288.
    MathSciNet     CrossRef

  17. N. Howgrave-Graham, A hybrid lattice-reduction and meet-in-the-middle attack against NTRU, in: Advances in Cryptology - CRYPTO 2007, Lecture Notes in Comput. Sci. 4622, Springer, Berlin, 2007, pp. 150-169.
    MathSciNet     CrossRef

  18. É. Jaulmes and A. Joux, A Chosen-Ciphertext Attack against NTRU, in: Advances in Cryptology - CRYPTO 2000, Lecture Notes in Comput. Sci. 1880, Springer, Berlin, 2000, pp. 20-35.
    MathSciNet     CrossRef

  19. M. Joye and J. J. Quisquater, On the importance of securing your bins: The garbage-man-in-the-middle attack, in: Proceedings of the 4th ACM conference on Computer and communications security, 1997, pp. 135-141.
    CrossRef

  20. A. A. Kamal and A. M. Youssef, A scan-based side channel attack on the NTRUEncrypt cryptosystem, in: 2012 Seventh International Conference on Availability, Reliability and Security, 2012, pp. 402-409.
    MathSciNet     CrossRef

  21. A. H. Karbasi and R. E. Atani, ILTRU: An NTRU-like public key cryptosystem over ideal lattices, IACR Cryptology ePrint Archive, 2015.

  22. A. H. Karbasi, R. E. Atani and S. E. Atani, PairTRU: Pairwise non-commutative extension of the NTRU public key cryptosystem, International Journal of Computer Applications 7 (1) (2018), 11-19.

  23. N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203-209.
    MathSciNet     CrossRef

  24. R. Kouzmenko, Generalizations of the NTRU cryptosystem, Diploma Project, École Polytechnique Fédérale de Lausanne (2005–2006).

  25. Z. Liu, Y. Pan and Z. Zhang, Cryptanalysis of an NTRU-based proxy encryption scheme from ASIACCS'15, in: Post-quantum cryptography, Lecture Notes in Comput. Sci. 11505 (2019), Springer, Cham, 2019, pp. 153-166.
    MathSciNet     CrossRef

  26. E. Malekian, A. Zakerolhosseini and A. Mashatan, QTRU: Quaternionic version of the NTRU public-key cryptosystems, ISeCure 3 (1) (2011), 28-42.

  27. R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, Deep Space Network Progress Report 44 (1978), 114-116.

  28. T. Meskanen and A. Renvall, A wrap error attack against NTRUEncrypt, Discrete Appl. Math. 154 (2006), 382-391.
    MathSciNet     CrossRef

  29. D. Micciancio, Closest Vector Problem, in: H.C.A. van Tilborg (ed.), Encyclopedia of Cryptography and Security, Springer, New York, 2005, pp. 79-80.
    CrossRef

  30. P. Mol and M. Yung, Recovering NTRU secret key from inversion oracles, in: Public key cryptography – PKC 2008, Lecture Notes in Comput. Sci. 4939, Springer, Berlin, 2008, pp. 18-36.
    MathSciNet     CrossRef

  31. M. Nevins, C. KarimianPour and A. Miri, NTRU over rings beyond Z, Des. Codes Cryptogr. 56 (2010), 65-78.
    MathSciNet     CrossRef

  32. D. Nunez, I. Agudo and J. Lopez, NTRUReEncrypt: An efficient proxy re-encryption scheme based on NTRU, in: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, Association for Computing Machinery, 2015, pp. 179-189.

  33. National Bureau of Standards, Data Encryption Standard, FIPS Publication 46, U.S. Department of Commerce, 1977.

  34. National Institute of Standards and Technology, Advanced Encryption Standard, FIPS Publication 197, U.S. Department of Commerce, 2001.

  35. Y. Pan and Y. Deng, A general NTRU-like framework for constructing lattice-based public-key cryptosystems, in: Information Security Applications, Lecture Notes in Comput. Sci. 7115, Springer, Berlin, 2012, pp. 109-120.
    CrossRef

  36. J. Proos, Imperfect decryption and an attack on the NTRU encryption scheme, IACR Eprint archive, 2003.

  37. R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (2) (1978), 120-126.
    MathSciNet     CrossRef

  38. T. E. Seidel, D. Socek and M. Sramka, Parallel symmetric attack on NTRU using nondeterministic lattice reduction, Des. Codes Cryptogr. 32 (2004), 369-379.
    MathSciNet     CrossRef

  39. C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948), 623-656.
    MathSciNet     CrossRef

  40. C. E. Shannon, Communication theory of secrecy systems, Bell System Tech. J. 28 (1949), 656-715.
    MathSciNet     CrossRef

  41. X. Shen, Z. Du and R. Chen, Research on NTRU algorithm for mobile Java security, in: 2009 International Conference on Scalable Computing and Communications; Eighth International Conference on Embedded Computing, 2009, pp. 366-369.
    CrossRef

  42. S. Singh and S. Padhye, Generalisations of NTRU cryptosystem, Security Comm. Network 9 (2016), 6315-6334.
    CrossRef

  43. W. A. Stein and others, Sage Mathematics Software (Version 9.0), The Sage Development Team, 2020, http://www.sagemath.org.

  44. J. Talbot and D. Welsh, Complexity and cryptography, Cambridge University Press, Cambridge, 2006.
    MathSciNet     CrossRef

  45. D. Welsh, Codes and cryptography, Clarendon Press, Oxford University Press, New York, 1988.
    MathSciNet

  46. H. Yassein and N. Al-Saidi, BITRU: Binary version of the NTRU public key cryptosystem via binary algebra, International Journal of Advanced Computer Science and Applications 7 (11) (2016), 1-6.
    CrossRef

Rad HAZU Home Page