PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem

Year 2018, Volume: 7 Issue: 1, 11 - 19, 01.03.2018

Amir Hassani Karbasi Reza Ebrahimi Atani Shahabaddin Ebrahimi Atani

Abstract

We show a novel lattice-based scheme PairTRU which is a non-commutative variant of the NTRU. The original NTRU is defined via the ring of quotient with variable in integers and this system works in the ring R = Z[x] . We extend this system over Z × Z and it performs all of operations in the non-commutative ring M = M k,Z×Z [x] < Ik×k,Ik×k xN − Ik×k,Ik×k > , where M is a matrix ring of k × k matrices of polynomials in R = Z×Z [x] < 1,1 xN − 1,1 > . In PairTRU, encrypting and decrypting are non-commutative and the cryptosystem is secure for linear algebra and Lattice-based attacks. PairTRU is designed using the NTRU core and reflects high levels of security by two-sided matrix multiplication with pairwise entries

Keywords

Public key cryptography, Lattice-based cryptosystem, NTRU, Matrix rings

References

• [1] R.A. Perlner, and D.A. Cooper, Quantum resistant public key cryptography: a survey, In: Proc. of IDtrust, ACM, New York, 2009, pp. 85–93.
• [2] J. Hoffstein, J. Pipher, and J.H. Silverman, NTRU: A Ring-Based Public Key Cryptosystem, Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, J.P. Buhler (ed.), LNCS 1423, Springer-Verlag, Berlin, 1998, pp. 267–288.
• [3] J. Hoffstein, J.H. Silverman, and W. Whyte, Estimated Breaking Times for NTRU Lattices, Technical Report #12, available at www.ntru.com.
• [4] I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography, Cambridge University Press, Cambridge, 1999.
• [5] http://www.ntru.com.
• [6] D. Coppersmith, and A. Shamir, Lattice attacks on NTRU, in EUROCRYPT ‘97, 1997, pp. 52–61.
• [7] C. Gentry, Key recovery and message attacks on NTRU-composite, In Eurocrypt ‘01, Springer LNCS 2045, 2001, pp. 182–194.
• [8] Standard Specifications for Public-Key Cryptographic Techniques Based on Hard Problems over Lattices. IEEE P1363, 2008. Available at http://grouper.ieee.org/groups/1363/.
• [9] D. Han, J. Hong, J.W. Han, and D. Kwon, Key recovery attacks on NTRU without ciphertext validation routine, In Proceeding of ACISP ‘03, LNCS, Springer-Verlag, vol. 2727, 2003, pp.274–284.
• [10] E. Jaulmes, and A. Joux, A Chosen Ciphertext Attack on NTRU, In Proceeding of CRYPTO ‘00, LNCS, Springer-Verlag, vol. 1880, 2000, pp. 20–35.
• [11] N. Howgrave-Graham, P.Q. Nguyen, D. Pointcheval, J. Proos, J.H. Silverman, A. Singer, and W. Whyte, The Impact of Decryption Failures on the Security of NTRU Encryption, In Proceeding of CRYPTO ‘03, LNCS, Springer-Verlag, vol. 2729, 2003, pp. 226–246.
• [12] P.Q. Nguyen, and D. Pointcheval, Analysis and Improvements of NTRU Encryption Paddings, In Proceeding of CRYPTO ‘02, LNCS, SpringerVerlag, vol. 2442, 2002, pp. 210–225.
• [13] P. Gaborit, J. Ohler, and P. Sole, CTRU, a polynomial analogue of NTRU, Tech- nical report, INRIA, France, 2002. Available at ftp://ftp.inria.fr/INRIA/publication/ publi-pdf/RR/RR-4621.pdf.
• [14] M. Coglianese, and B.M. Goi, MaTRU: A New NTRU-Based Cryptosystem, In Proceedings of the 6th International Conference on Cryptology in India (INDOCRYPT), 2005, pp. 232–243.
• [15] N. Vats, NNRU, a Noncommutative Analogue of NTRU, The Computing Research Repos- itory (CoRR), abs/0902.1891, 2009. Available at http://arxiv.org/abs/0902.1891.
• [16] R. Kouzmenko, Generalizations of the NTRU Cryptosystem, Master’s thesis, Polytechnique Montreal, Canada, 2006.
• [17] C. Karimianpour, Lattice-Based Cryptosystems, Master’s thesis, University of Ottawa, Canada, 2007.
• [18] M. Nevins, C. Karimianpour, and A. Miri, NTRU over rings beyond Z, Designs, Codes and Cryptography, vol. 56, no. 1, 2010, pp. 65–78.
• [19] E. Malekian, A. Zakerolhosseini, and A. Mashatan, QTRU: Quaternionic Version of the NTRU Public-Key Cryptosystems, The int’l Journal of information Security (ISeCure), vol. 3, no. 1, 2011, pp. 29–42.
• [20] A.H. Karbasi and R.E. Atani, ILTRU: An NTRU-Like Public Key Cryptosystem Over Ideal Lattices, IACR Cryptology ePrint Archive 2015: 549, 2015.
• [21] M.P. Karampetakis, and P. Tzekis, On computation of the genralized inverse of a polynomial matrix, IMA, vol. 18, 2001, pp. 83–97.
• [22] N. Howgrave-Graham, J.H. Silverman, and W. Whyte, A MeetIn-The-Middle Attack on an NTRU Private Key, Technical report, Security Innovation Inc., Boston, MA, USA, 2002. Available at http://securityinnovation.com/cryptolab/pdf/NTRUTech004v2.pdf.
• [23] E. Jaulmes, and A. Joux, A Chosen Ciphertext Attack against NTRU, In Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO ‘00), 2000, pp. 20–36.
• [24] J. Hoffstein, and J.H. Silverman, Optimizations for NTRU, Technical Report 015, NTRU Cryptosystems, 2000. Available at http://www.sisecure.com/cryptolab/pdf/ TECH-ARTICLE-OPT.pdf.
• [25] P.Q. Nguyen, and D. Stehle´, LLL on the Average, In Proceedings of the 7th International Symposium on Algorithmic Number Theory (ANTSVII )., 2006, pp. 238–256.
• [26] P.Q. Nguyen, and D. Stehle´, Low Dimensional Lattice Basis Reduction Revisited, ACM Transactions on Algorithms, vol. 5, no. 4, 2009, pp.1– 48.
• [27] A.H. Karbasi and R.E. Atani, PSTRU: A provably secure variant of NTRUEncrypt over extended ideal lattices, The 2nd National Industrial Mathematics Conference, Tabriz, Iran, 2015.
• [28] A.H. Karbasi and R.E. Atani, A Survey on Lattice-based Cryptography, (In Persian), Biannual Journal for Cyberspace Security (Monadi AFTA), Vol. 3, No. 1, 2015, pp 3–14. Available from: http://monadi.isc.org.ir/browse.php?a id=23&sid=1&slc lang=en
• [29] S.E. Atani, R.E. Atani, and A.H. Karbasi, NETRU: A Non-Commutative and Secure Variant of CTRU Cryptosystem, The ISC international journal of information security (IseCure), to appear.
• [30] S.E. Atani, R.E. Atani, and A.H. Karbasi, EEH: A GGH-Like Public Key Cryptosystem Over The Eisenstein Integers Using Polynomial Representations, The ISC international journal of information security (IseCure), Vol 7, No. 2, 2015, pp. 115–126.
• [31] A.H. Karbasi, R.E. Atani, and S.E. Atani, A New Ring-Based SPHF and PAKE Protocol On Ideal Lattices, Submitted.
• [32] A.H. Karbasi, M.A. Nia, and R.E. Atani, Designing of An Anonymous Communication System Using Lattice-based Cryptography, Journal of Electronic and Cyber Defence, Vol. 2, No. 3, 2014, pp. 13–22, Persian.
• [33] S.E. Atani, R.E. Atani, and A.H. Karbasi, A Provably Secure Variant of ETRU Based on Extended Ideal Lattices over Direct Product of Dedekind domains, Submitted.
• [34] S. Singh and P. Sahadeo, Generalisations of NTRU cryptosystem, Security and Communication Networks, DOI: 10.1002/sec.1693, 2016.