Enhanced Provably Secure NTRU Encryption Based on Hard Learning over Rings

Abstract:

Since the presentation of NTRU public-key cryptosystem by Hoffstein, Pipher and Silverman, its favorable properties, such as easily created keys, high speed, excellent performance and conjectured resistance to quantum computers, have made it to be of great use. This paper proposes an enhanced scheme based on the hard learning with error over ring (R-LWE) problem to improve the security of the modified NTRUEncrypt presented by Stehle and Steinfled. We used part of the padding ideas of Fujisaki and Okamoto to obtain this scheme. It is semantically secure in strong sense of indistinguishability against adaptive chosen-ciphertext attacks in the random oracle model assuming the quantum hardness of standard worst-case problem over ideal lattices. It is also possible to arbitrarily decrease the error probability, and even to eliminate it completely. We gave the detailed analysis using the known results from classic works. Furthermore, this scheme owns many advantages such as the uniformity of public key, usual assumptions and the freedom for coding messages.

• Periodical: Applied Mechanics and Materials (Volumes 236-237)
• Pages: 1139-1144
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.236-237.1139
• Online since: November 2012
• Authors: Wu Yan Fang, Zheng Huang, Wang Li Cheng, Wen Qiao Yan
• Keywords: Indistinguishability, Lattice-Based Cryptography, NTRUEncrypt

References

[1] D. Coppersmith, A. Shamir, Lattice Attacks on NTRU, Advances in Cryptology EUROCRYPT. Berlin Heidelberg: Springer-Verlag, LNCS, 1997, 1233: 52-61.

DOI: 10.1007/3-540-69053-0_5

[2] J. Hoffstein, J Pipher, J. Silverman, NTRU: A Ring Based Public Key Cryptosystem, Proceedings of ANTS 3 (1998), Berlin Heidelberg: Springer-Verlag, LNCS, 1998, 1423: 267-288.

DOI: 10.1007/bfb0054868

[3] T. Meskanen, A. Renvall, A wrap error attack against NTRUEncrypt, Discrete Applied Mathematics, 2006, 154(2): 382–391.

DOI: 10.1016/j.dam.2005.03.019

[4] C. Gentry, Key recovery and message attacks on NTRU-composite, International Conference on the Theory and Application of Cryptographic Techniques, Advances in Cryptology EUROCRYPT 2001: 182-194.

DOI: 10.1007/3-540-44987-6_12

[5] E. Jaulmes, A. Joux, A Chosen-Ciphertext Attack against NTRU, Proceedings of Crypto'00, Berlin Heidelberg: Springer-Verlag, LNCS, 2000, 1880: 20-35.

DOI: 10.1007/3-540-44598-6_2

[6] N. Gama, P. Q. Nguyen, New Chosen-Ciphertext Attacks on NTRU, 10th International Conference on Practice and Theory in Public-key Cryptography, Berlin, Heidelberg: Springer-Verlag, 2007: 89-106.

DOI: 10.1007/978-3-540-71677-8_7

[7] J. Hoffstein, J H. Sliverman, Optimizations for NTRU, Proceedings of the International Conference on Public-key Cryptography and Computation Number Theory. Berlin, NewYork : De Gruyter, (2001).

[8] J. Hoffstein, J. H. Silverman, Protecting NTRU against chosen ciphertext and reaction attacks, Technical report, NTRU Cryptosystems, (2000).

[9] P. Nguyen, D. Pointcheval, Analysis and improvements of NTRU encryption paddings, In Advances in Cryptology-CRYPTO2002, Berlin Heidelberg: Springer-Verlag, LNCS, 2002, 2442: 210-225.

DOI: 10.1007/3-540-45708-9_14

[10] D. Stehle, R. Steinfeld, Making NTRU as Secure as Worst-case Problems over Ideal Lattice, EUROCRYPT (2010). Berlin Heidelberg: Springer-Verlag, LNCS, 2011, 6630: 27-47.

DOI: 10.1007/978-3-642-20465-4_4

[11] R. A. Perlner, D. A. Cooper, Quantum resistant public key cryptographer: a survey, Proceedings of IDtrust '09, New York: ACM, 2009: 85-93.

[12] C. Peikert, B. Waters, Lossy trapdoor functions and their applications, Proceedings of the 40th ACM Symp. on Theory of Computing(STOC), 2008: 187-196.

DOI: 10.1145/1374376.1374406

[13] C. Peikert, Public-key cryptosystem form the worst-case shortest vector problem, Proceedings of 41st ACM Symp. on Theory of Computing(STOC), (2009).

DOI: 10.1145/1536414.1536461

[14] E. Fujisaki, T. Okamoto, Secure integration of asymmetric and symmetric encryption scheme, Proceedings of Crypto'99, Berlin Heidelberg: Springer-Verlag, LNCS, 1999, 1666: 537-554.

DOI: 10.1007/3-540-48405-1_34

[15] D. Micciancio, S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective, The Kluwer International Series in Engineering and Computer Science. Boston, Massachusetts: Kluwer Academic Publishers, 2002, 671.

[16] D. Micciancio, Generalized compact knapsacks, cyclic lattice, and efficient one-way functions, Computational Complexity, 2007, 16 (4): 365-411.

DOI: 10.1007/s00037-007-0234-9

[17] D. Micciancio, O. Regev, Worst-case to average case reduction based on Gaussian measures, SIAM Jounal on Computing, 2007, 37 (1): 267-302. Preliminary version in FOCS (2004).

DOI: 10.1137/s0097539705447360

[18] V Lyubashevsky, C. Peikert and O. Regve, On ideal lattice and learning with errors over rings, EUROCRYPT 2010. Berlin Heidelberg: Springer-Verlag, LNCS, 2010, 6110: 1-23.

DOI: 10.1007/978-3-642-13190-5_1

[19] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM, 2009, 56 (6): 34. Preliminary version in STOS'05.

DOI: 10.1145/1568318.1568324

[20] Nick Howgrave-Graham, J, H. Silverman and W. Whyte, Choosing Parameters Sets for NTRUEncrypt with NAEP and SVES-3, Proceedings of CT-RSA (2005), Berlin Heidelberg: Springer-Verlag, LNCS, 1997, 3376: 118-136.

DOI: 10.1007/978-3-540-30574-3_10