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

Amir Hassani Karbasi; Reza Ebrahimi Atani; Shahabaddin Ebrahimi Atani

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

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.

Details

Primary Language

English

Subjects

-

Journal Section

-

Authors

Amir Hassani Karbasi This is me

Reza Ebrahimi Atani This is me

Shahabaddin Ebrahimi Atani This is me

Publication Date

March 1, 2018

Submission Date

-

Acceptance Date

-

Published in Issue

Year 2018 Volume: 7 Number: 1

IZ

https://izlik.org/JA83KS83KP

Cite

RIS / Bibtex

APA

Karbasi, A. H., Atani, R. E., & Atani, S. E. (2018). PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem. International Journal of Information Security Science, 7(1), 11-19. https://izlik.org/JA83KS83KP

AMA

1.Karbasi AH, Atani RE, Atani SE. PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem. IJISS. 2018;7(1):11-19. https://izlik.org/JA83KS83KP

Chicago

Karbasi, Amir Hassani, Reza Ebrahimi Atani, and Shahabaddin Ebrahimi Atani. 2018. “PairTRU: Pairwise Non-Commutative Extension of The NTRU Public Key Cryptosystem”. International Journal of Information Security Science 7 (1): 11-19. https://izlik.org/JA83KS83KP.

EndNote

Karbasi AH, Atani RE, Atani SE (March 1, 2018) PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem. International Journal of Information Security Science 7 1 11–19.

IEEE

[1]A. H. Karbasi, R. E. Atani, and S. E. Atani, “PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem”, IJISS, vol. 7, no. 1, pp. 11–19, Mar. 2018, [Online]. Available: https://izlik.org/JA83KS83KP

ISNAD

Karbasi, Amir Hassani - Atani, Reza Ebrahimi - Atani, Shahabaddin Ebrahimi. “PairTRU: Pairwise Non-Commutative Extension of The NTRU Public Key Cryptosystem”. International Journal of Information Security Science 7/1 (March 1, 2018): 11-19. https://izlik.org/JA83KS83KP.

JAMA

1.Karbasi AH, Atani RE, Atani SE. PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem. IJISS. 2018;7:11–19.

MLA

Karbasi, Amir Hassani, et al. “PairTRU: Pairwise Non-Commutative Extension of The NTRU Public Key Cryptosystem”. International Journal of Information Security Science, vol. 7, no. 1, Mar. 2018, pp. 11-19, https://izlik.org/JA83KS83KP.

Vancouver

1.Amir Hassani Karbasi, Reza Ebrahimi Atani, Shahabaddin Ebrahimi Atani. PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem. IJISS [Internet]. 2018 Mar. 1;7(1):11-9. Available from: https://izlik.org/JA83KS83KP