PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem
PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem
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
___
- [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.