QTRU: quaternionic version of the NTRU public-key cryptosystems

Document Type: ORIGINAL RESEARCH PAPER

Authors

Abstract

In this paper we will construct a lattice-based public-key cryptosystem using non-commutative quaternion algebra, and since its lattice does not fully fit within Circular and Convolutional Modular Lattice (CCML), we prove it is arguably more secure than the existing lattice-based cryptosystems such as NTRU. As in NTRU, the proposed public-key cryptosystem relies for its inherent security on the intractability of finding the shortest vector in a certain non-convolutional modular lattice, yet it is efficient and cost effective, contrary to cryptosystems such as RSA or ECC. The detailed specification of the proposed cryptosystem, including the underlying algebraic structure, key generation, encryption and decryption process and also the issues regarding key security, message security, and probability of successful decryption are explained. We will further show, based on the existing results for lattice-reduction algorithms, that the proposed cryptosystem with a dimension of 41 will have a security equal to NTRU-167.

Keywords


[1] Neal Koblitz and Alfred J. Menezes. A Survey of Public-Key Cryptosystems. SIAM Review, 46(4):599-634, 2004.

[2] Neal Koblitz and Alfred Menezes. The Brave New World of Bodacious Assumptions in Cryptography. Notices of the American Mathematical Society, 57(3):357-365, 2010.

[3] Miklós Ajtai. The Shortest Vector Problem in L2 Is NP-Hard for Randomized Reductions. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC'98), pages 10-19, 1998.

[4] Daniele Micciancio. The Shortest Vector Problem Is NP-Hard to Approximate to within Some Constant. SIAM Journal on Computing, 30(6):2008-2035, 2001. Preliminary version in FOCS 1998.

[5] Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems: A Cryptographic Perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, MA, USA, 2002.

[6] Phong Q. Nguyen and Jacques Stern. The Two Faces of Lattices in Cryptology. In Revised Papers from the International Conference on Cryptography and Lattices (CaLC'01), pages 146-180, 2001.

[7] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A Ring-Based Public Key Cryptosystem. In Proceedings of the 3rd International Symposium on Algorithmic Number Theory (ANTS-III), pages 267-288, 1998.

[8] Jeffrey Hoffstein and Joseph Silverman. Optimizations for NTRU. Technical Report 015, NTRU Cryptosystems, 2000. Available at http://www.sisecure.com/cryptolab/pdf/TECH_ARTICLE_OPT.pdf.

[9] Philip S. Hirschhorn, Jeffrey Hoffstein, Nick Howgrave-Graham, and William Whyte. Choosing NTRUEncrypt Parameters in Light of Combined Lattice Reduction and MITM Approaches. In Proceedings of the 7th International Conference on Applied Cryptography and Network Security (ACNS'09 ), pages 437-455, 2009.

[10] Petros Mol and Moti Yung. Recovering NTRU Secret Key from Inversion Oracles. In Proceedings of the 11th International Conference on Public

Key Cryptography (PKC'08), pages 18-36, 2008.

[11] Standard Specifications for Public-Key Cryptographic Techniques Based on Hard Problems over Lattices. IEEE P1363, 2008. Available at http://grouper.ieee.org/groups/1363/.

[12] Daniel V. Bailey, Daniel Coffin, Adam Elbirt, Joseph H. Silverman, and Adam D. Woodbury. NTRU in constrained devices. In Proceedings of the 3rd International Workshop on Cryptographic Hardware and Embedded Systems (CHES'01), pages 262-272, 2001.

[13] Colleen O'Rourke and Berk Sunar. Achieving NTRU with Montgomery Multiplication. IEEE Transactions on Computers, 52:440-448, 2003.

[14] Philippe Gaborit, Julien Ohler, and Patrick Solé. CTRU, a polynomial analogue of NTRU. Technical report, INRIA, France, 2002. Available at ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-4621.pdf.

[15] Michael Coglianese and Bok-Min Goi. MaTRU: A New NTRU-Based Cryptosystem. In Proceedings of the 6th International Conference on Cryptology in India (INDOCRYPT), pages 232-243, 2005.

[16] Nitin Vats. NNRU, a Noncommutative Analogue of NTRU. The Computing Research Repository (CoRR), abs/0902.1891, 2009. Available athttp://arxiv.org/abs/0902.1891.

[17] R. Kouzmenko. Generalizations of the NTRU Cryptosystem. Master's thesis, Polytechnique Montreal, Canada, 2006.

[18] Camelia Karimianpour. Lattice-Based Cryptosystems. Master's thesis, University of Ottawa, Canada, 2007.

[19] Monica Nevins, Camelia Karimianpour, and Ali Miri. NTRU over rings beyond Z. Designs, Codes and Cryptography, 56(1):65-78, 2010.

[20] Jeffrey Hoffstein, Jill Pipher, and J.H. Silverman. An Introduction to Mathematical Cryptography. Springer-Verlag, 1st edition, 2008.

[21] Jill Pipher. Lectures on the NTRU Encryption Algorithm and Digital Signature Scheme. Technical report, Brown University, Providence, Rhode Island, 2005. Available at http://www.math.brown.edu/~jpipher/grenoble.pdf.

[22] Alexander May and Joseph H. Silverman. Dimension Reduction Methods for Convolution Modular Lattices. In Revised Papers from the International Conference on Cryptography and Lattices (CaLC'01), pages 110-125, 2001.

[23] Don Coppersmith and Adi Shamir. Lattice Attacks on NTRU. In International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT), pages 52-61, 1997.

[24] Nick Howgrave-Graham, Jeff Hoffstein, Jill Pipher, and William Whyte. On Estimating the Lattice Security of NTRU. Technical report, Brown University, Providence, Rhode Island, 2005. Available at http://www.math.brown.edu/~jpipher/NTRULattice-2005-1.pdf.

[25] Alexander May. Cryptanalysis of NTRU, 1999. Available at http://www.informatik.uni-frankfurt.de/~alex/ntru.ps.

[26] Joseph H. Silverman. Dimension-Reduced Lattices, Zero-Forced Lattices, and the NTRU Public Key Cryptosystem. Technical report, Security Innovation Inc., Boston, MA, USA, 1999. Available at http://securityinnovation.com/cryptolab/pdf/NTRUTech013.pdf.

[27] Nicolas Gama and Phong Q. Nguyen. Predicting Lattice Reduction. In International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT), pages 31-51, 2008.

[28] A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring Polynomials with Rational Coefficients. Mathematische Annalen, 261(4):515-534, 1982.

[29] Nicolas Gama, Nick Howgrave-Graham, and Phong Q. Nguyen. Symplectic Lattice Reduction and NTRU. In International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT), pages 233-253, 2006.

[30] Tommi Meskanen. On the NTRU Cryptosystem. PhD thesis, University of Turku, Finland, 2005.

[31] John H. Conway and Derek A. Smith. On Quaternions and Octonions: Their Geometry, Arithmetic, and Symmetry. A. K. Peters, Ltd., 2003.

[32] David Lewis. Quaternion Algebras and the Algebraic Legacy of Hamilton. Irish Mathematical Society Bulletin, 57:41-64, 2006.

[33] Joseph J. Rotman. Advanced Modern Algebra. Prentice Hall, 2002.

[34] Zi Yang Sham. Quaternion Algebras and Quadratic Forms. Master's thesis, University of Waterloo, Ontario, Canada, 2008.

[35] Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.

[36] Nick Howgrave-Graham, Joseph H. Silver-man, and William Whyte. A Meet-In-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.

[37] Eliane Jaulmes and Antoine Joux. A Chosen Ciphertext Attack against NTRU. In Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO'00), pages 20-36, 2000.

[38] Phong Q. Nguyen and Damien Stehlé. LLL on the Average. In Proceedings of the 7th International Symposium on Algorithmic Number Theory (ANTS-VII)., pages 238-256, 2006.

[39] Phong Q. Nguyen and Damien Stehlé. Low-Dimensional Lattice Basis Reduction Revisited. ACM Transactions on Algorithms, 5(4):1-48, 2009.

[40] Michael Schneider, Johannes Buchmann, and Richard Lindner. Probabilistic Analysis of LLL Reduced Bases. In Western European Workshop on Research in Cryptology (WEWoRC), volume 6429 of LNCS. Springer, 2009.

[41] Nick Howgrave-Graham, Jeff Hoffstein, JillPipher, and William Whyte. On Estimating the Lattice Security of NTRU. Cryptology ePrint Archive, Report 2005/104, 2005. Available at http://eprint.iacr.org/2005/104.

[42] Jeffrey Hoffstein and Joseph H. Silverman. A Non-Commutative Version of the NTRU Public Key Cryptosystem, 1997. Unpublished Paper.

[43] Kathryn Rendall Truman. Analysis and Extension of Non-Commutative NTRU. PhD thesis, University of Maryland, MD, USA, 2007.

[44] Don Coppersmith. Attacking Non-Commutative NTRU. Technical report, IBM, 1997.