A Provably Secure Variant of ETRU Based on Extended Ideal Lattices Over Direct Product of Dedekind Domains

Document Type : Research Article

Authors

1 Department of Computer Engineering, University of Guilan, P. O. Box 3756, Rasht, Iran.

2 Department of Mathematics, University of Guilan, P. O. Box 1914, Rasht, Iran.

Abstract

Jarvis and Nevins presented ETRU in 2013 which has applausive performance with moderate key-sizes and conjectured resistance to quantum computers. ETRU, as an efficient NTRUEncrypt-like cryptosystem, is over the ring of Eisenstein integers that is faster with smaller keys for the same or better level of security than does NTRUEncrypt which is a desirable alternative to public-key cryptosystems based on factorisation and discrete logarithm problem. However, because of its construction, doubts have regularly arisen on its security. In this paper, we propose how to modify ETRU to make it provably secure, under our modified assumption of quantum hardness of standard worst-case lattice problems, restricted to extended ideal lattices related to some extensions of cyclotomic fields structures. We describe the structure of all generated polynomial rings of quotient over direct product of Dedekind domains Z and Z[ζ3], where ζ3 is complex cube root of unity. We give a detailed description to show that if the private key polynomials of the ETRU are selected from direct product of some Dedekind domains using discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its range. The security then proves for our main system from the already proven hardness of the R-SIS and R-LWE problems by their extensions.

Keywords

References

[1] J. Hoffstein, J. Pipher, , and J. H. Silverman. NTRU: a new high speed public key cryptosystem. In presented at the rump session of Crypto'96, 1996.
[2] J. Hoffstein, J. Pipher, and J. H. Silverman. NTRU: a ring based public key cryptosystem. In International Algorithmic Number Theory Symposium, pages 267--288. Springer, Berlin, Heidelberg, 1998. [ DOI ]
[3] IEEE Standard Specifications for Public-Key Cryptography. IEEE Std 1363-2000, pages 1--228, Aug 2000. [ DOI ]
[4] Ray A. Perlner and D. A. Cooper. Quantum resistant public key cryptography: a survey. In Proceedings of the 8th Symposium on Identity and Trust on the Internet, pages 85--93. ACM, 2009. [ DOI ]
[5] J. Hoffstein, J. P., and J. H. Silverman. NSS: An NTRU Lattice-Based Signature Scheme. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 211--228. Springer, Berlin, Heidelberg, 2001. [ DOI ]
[6] M. Szydlo. Hypercubic Lattice Reduction and Analysis of GGH and NTRU Signatures. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 433--448. Springer, Berlin, Heidelberg, 2003. [ DOI ]
[7] S. Min, G. Yamamoto, and K. Kim. Weak property of malleability in NTRUSign. In Australasian Conference on Information Security and Privacy, pages 379--390. Springer, Berlin, Heidelberg, 2004. [ DOI ]
[8] P. Q. Nguyen and O. Regev. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. Journal of Cryptology, 22(2):139–160, 2009. [ DOI ]
[9] V. Lyubashevsky and D. Micciancio. Generalized compact knapsacks are collision resistant. In International Colloquium on Automata, Languages, and Programming, pages 144--155. Springer, Berlin, Heidelberg, 2006. [ DOI ]
[10] C. Peikert and A. Rosen. Lattices that admit logarithmic worst-case to average-case connection factors. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 478--487. ACM, 2007. [ DOI ]
[11] C. Peikert and A. Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In Theory of Cryptography Conference, pages 145--166. Springer, Berlin, Heidelberg, 2006. [ DOI ]
[12] V. Lyubashevsky, D. Micciancio, C. Peikert, and A. Rosen. SWIFFT: a modest proposal for FFT hashing. In International Workshop on Fast Software Encryption, pages 54--72. Springer, Berlin, Heidelberg, 2008. [ DOI ]
[13] V. Lyubashevskyand C. Peikert and O. Regev. On ideal lattices and learning with errors over rings. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 1--23. Springer, Berlin, Heidelberg, 2010. [ DOI ]
[14] O. Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6), 2009. [ DOI ]
[15] D. Stehlé, R. Steinfeld, K. Tanaka, and K. Xagawa. Efficient public key encryption based on ideal lattices. In International Conference on the Theory and Application of Cryptology and Information Security, pages 617--635. Springer, Berlin, Heidelberg, 2009. [ DOI ]
[16] C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 197--206. ACM, 2008. [ DOI ]
[17] V. Lyubashevsky. Fiat-shamir with aborts: Applications to lattice and factoring-based signatures. In International Conference on the Theory and Application of Cryptology and Information Security, pages 598--616. Springer, Berlin, Heidelberg, 2009. [ DOI ]
[18] P.L Cayrel, R. Lindner, M. Rückert, and R. Silva. A lattice-based threshold ring signature scheme. In International Conference on Cryptology and Information Security in Latin America, pages 255--272. Springer, Berlin, Heidelberg, 2010. [ DOI ]
[19] D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert. Bonsai trees, or how to delegate a lattice basis. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 523--552. Springer, Berlin, Heidelberg, 2010. [ DOI ]
[20] C. Gentry. Toward basing fully homomorphic encryption on worst-case hardness. In Annual Cryptology Conference, pages 116--137. Springer, Berlin, Heidelberg, 2010. [ DOI ]
[21] C. Gentry and S. Halevi. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits. In IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 107--109. IEEE, 2011. [ DOI ]
[22] V. Vaikuntanathan Z. Brakerski, C. Gentry. Fully homomorphic encryption without bootstrapping. Cryptology ePrint Archive, 18, 2011.
[23] V. Lyubashevsky. Lattice-based identification schemes secure under active attacks. In International Workshop on Public Key Cryptography, pages 162--179. Springer, Berlin, Heidelberg, 2008. [ DOI ]
[24] A. Kawachi, K. Tanaka, and K. Xagawa. Concurrently secure identification schemes and ad hoc anonymous identification schemes based on the worst-case hardness of lattice problems. In International Conference on the Theory and Application of Cryptology and Information Security, pages 372--389. Springer, Berlin, Heidelberg, 2008. [ DOI ]
[25] C. Peikert and V. Vaikuntanathan. Noninteractive statistical zero-knowledge proofs for lattice problems. In Annual International Cryptology Conference, pages 536--553. Springer, Berlin, Heidelberg, 2008. [ DOI ]
[26] Philippe Gaborit, Julien Ohler, and Patrick Solé. CTRU, a polynomial analogue of NTRU. Technical Report RR-4621, INRIA, November 2002. [ http | .pdf ]
Keywords: POPOV NORMAL FORM ; VARSHAMOV GILBERT BOUND ; CRYPTOGRAPHY ; NTRU
[27] M. Coglianese and B.M. Goi. MaTRU: A New NTRU-Based Cryptosystem. In International Conference on Cryptology in India, pages 232--243. Springer, Berlin, Heidelberg, 2005. [ DOI ]
[28] N. Vats. NNRU, a Noncommutative Analogue of NTRU. arXiv preprint arXiv:0902.1891, 2009.
[29] R. Kouzmenko. Generalizations of the NTRU Cryptosystem. PhD thesis, Master’s thesis, Polytechnique Montreal, Canada, 2005.
[30] M. EHSAN, Z. ALI, and M. ATEFEH. QTRU: Quaternionic Version of the NTRU Public-Key Cryptosystems. The ISC International Journal of Information Security, 3(1):29--42, 2011. [ DOI ]
[31] A. H. Karbasi and R. E. Atani. ILTRU: An NTRU-Like Public Key Cryptosystem Over Ideal Lattices. IACR Cryptology ePrint Archive, 2015:549, 2015. [ DOI ]
[32] A.H. Karbasi and R.E. Atani. A Survey on Lattice-based Cryptography. Biannual Journal for Cyberspace Security (Monadi AFTA), 3(1):3--14, 2015.
[33] M. Ajtai. Generating hard instances of lattice problems (extended abstrat). In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 99--108. ACM, 1996. [ DOI ]
[34] O. Regev. The learning with errors problem. http://www.cs.tau.ac.il/~odedr/, Date Accessed: 2010.
[35] M. EHSAN, Z. ALI, and M. ATEFEH. Generalized compact knapsacks,cyclic lattices, and efficient one-way functions. computational complexity, 16(4):365–411, 2007. [ DOI ]
[36] D. Stehlé and R. Steinfeld. Making NTRUEncrypt and NTRUSign as secure as standard worst-case problems over ideal lattices. In Proceedings of the 30th Annual international conference on Theory and applications of cryptographic techniques: advances in cryptology, pages 27--47. ACM, 2011.
[37] C. Peikert. An efficient and parallel gaussian sampler for lattices. In Annual Cryptology Conference, pages 80--97. Springer, Berlin, Heidelberg, 2010. [ DOI ]
[38] L. Ducas and P. Q. Nguyen. Faster gaussian lattice sampling using lazy floating-point arithmetic. In International Conference on the Theory and Application of Cryptology and Information Security, pages 415--432. Springer, Berlin, Heidelberg, 2012. [ DOI ]
[39] N. H. Graham, J. H. Silverman, A. Singer, and W. Whyte. NAEP: Provable security in the presence of decryption failures. International Association for Cryptologic Research, 2003, 2003.
[40] R. Steinfeld, S. Ling, J. Pieprzyk, C. Tartary, and H. Wang. NTRUCCA: How to Strengthen NTRUEncrypt to Chosen-Ciphertext Security in the Standard Model. In International Workshop on Public Key Cryptography, pages 353--371. Springer, Berlin, Heidelberg, 2012. [ DOI ]
[41] A. L. Alt, E. Tromer, and V. Vaikuntanathan. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1219--1234. ACM, 2012. [ DOI ]
[42] K. Jarvis and M. Nevins. ETRU: NTRU over the Eisenstein Integers. Designs Codes and Cryptography, 47(1), 2013. [ DOI ]
[43] D. Micciancio and O. Regev. Worst-case to average-case reductions based on gaussian measures. SIAM Journal on Computing, 37(1):267–302, 2007. [ DOI ]
[44] A.H. Karbasi and R.E. Atani. PSTRU: A provably secure variant of NTRUEncrypt over extended ideal lattices. In The 2nd National Industrial Mathematics Conference, Tabriz, Iran, 2015.
[45] K. Jarvis. NTRU over the Eisenstein integers. PhD thesis, University of Ottawa, 2011.
[46] H. Cohen. Advanced topics in computational number theory. Springer, 2000.
[47] C. Fieker and D. Stehlé. Short bases of lattices over number fields. In International Algorithmic Number Theory Symposium, pages 157--173. Springer, Berlin, Heidelberg, 2010. [ DOI ]
[48] A. K. Lenstra, H. W. LenstraJr, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982. [ DOI ]
[49] C. P. Schnorr. A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Computer Science, 53(2):201--224, 1987. [ DOI ]
[50] D. Micciancio and P. Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. SIAM Journal on Computing, 17(3):351--358, 2010. [ DOI ]
[51] B. Applebaum, D. Cash, C. Peikert, and A. Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In Annual International Cryptology Conference, pages 595--618. Springer, Berlin, Heidelberg, 2009. [ DOI ]
[52] V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. Journal of the ACM (JACM), 60(6):43, 2013.
[53] V. Lyubashevsky, C. Peikert, and O. Regev. A toolkit for Ring-LWE cryptography. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 35--54. Springer, Berlin, Heidelberg, 2013. [ DOI ]
[54] L. Ducas and A. Durmus. Ring-LWE in polynomial rings. In International Workshop on Public Key Cryptography, pages 34--51. Springer, Berlin, Heidelberg, 2012. [ DOI ]
[55] P. Garrett. Abstract Algebra. Technical report, University of Minnesota, 2007. [ .pdf ]
[56] R. Lindner and C. Peikert. Better key sizes (and attacks) for LWE-based encryption. In Cryptographers’ Track at the RSA Conference, pages 319--339. Springer, Berlin, Heidelberg, 2011. [ DOI ]
[57] D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 700--718. Springer, Berlin, Heidelberg, 2012. [ DOI ]
[58] D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert. Bonsai trees, or how to delegate a lattice basis. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 523--552. Springer, Berlin, Heidelberg, 2010. [ DOI ]
[59] S. Agrawal, D. Boneh, and X. Boyen. Efficient lattice (H)IBE in the standard model. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 553--572. Springer, Berlin, Heidelberg, 2010. [ DOI ]
[60] S. Agrawal, D. Boneh, and X. Boyen. Lattice basis delegation in fixed dimension and shorter ciphertext hierarchical IBE. In Annual Cryptology Conference, pages 98--115. Springer, Berlin, Heidelberg, 2010. [ DOI ]
[61] Z. Brakerski and V. Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 97--106. IEEE, 2011. [ DOI ]
[62] Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 309--325. Springer, Berlin, Heidelberg, 2012. [ DOI ]
[63] X. Boyen. lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more. In International Workshop on Public Key Cryptography, pages 499--517. Springer, Berlin, Heidelberg, 2010. [ DOI ]
[64] V. Lyubashevsky. Lattice signatures without trapdoors. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 738--755. Springer, Berlin, Heidelberg, 2012. [ DOI ]
[65] B. Rajabi and Z. Eslami. A CCA2-Secure Incomparable Public Key Encryption Scheme. Journal of Computing and Security, 3(1):3--12, 2016.
[66] J. Alizadeh and M. R. Aref. JHAE: A Novel Permutation-Based Authenticated Encryption Mode Based on the Hash Mode JH. Journal of Computing and Security, 2(1):3--20, 2015.
[67] S. Khodambashi and A. Zakerolhosseini. A Weak Blind Signature Based on Quantum Key Distribution. Journal of Computing and Security, 1(3):179--186, 2014.
[68] A. H. Karbasi, S. E. Atani, and R. E. Atani. PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem. Journal of Computing and Security, 7(1):201--224, 2018.
[69] R. E. Atani, S. E. Atani, and A. H. Karbasi. NETRU: A Non-commutative and Secure Variant of CTRU Cryptosystem. International Journal of Information Security, 10(1):45--53, 2018.
Journal of Computing and Security
Volume 5, Issue 1 - Serial Number 1
January 2018
Pages 13-34

Files

History

  • Receive Date: 02 November 2016
  • Revise Date: 06 July 2018
  • Accept Date: 01 September 2018

Share

How to cite

Statistics