×

Choosing parameters for NTRUEncrypt. (English) Zbl 1383.94022

Handschuh, Helena (ed.), Topics in cryptology – CT-RSA 2017. The cryptographers’ track at the RSA conference 2017, San Francisco, CA, USA, February 14–17, 2017. Proceedings. Cham: Springer (ISBN 978-3-319-52152-7/pbk; 978-3-319-52153-4/ebook). Lecture Notes in Computer Science 10159, 3-18 (2017).
Summary: We describe a method for generating parameter sets, and calculating security estimates, for NTRUEncrypt. Our security analyses consider lattice attacks, the hybrid attack, subfield attacks, and quantum search. Analyses are provided for the IEEE 1363.1-2008 product-form parameter sets, for the NTRU Challenge parameter sets, and for two new parameter sets. These new parameter sets are designed to provide \(\geq 128\)-bit post-quantum security.
For the entire collection see [Zbl 1356.94003].

MSC:

94A60 Cryptography

Software:

NTRU; GitHub; BKZ
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] NTRU OpenSource Project.online. https://github.com/NTRUOpenSourceProject/ntru-crypto
[2] 2015. https://www.ntru.com/ntru-challenge/
[3] Bernstein, D.J.: Cost analysis of hash collisions: will quantum computers makeSHARCS obsolete? (2009). http://cr.yp.to/papers.html#collisioncost
[4] Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-25385-0_1 · Zbl 1227.94037 · doi:10.1007/978-3-642-25385-0_1
[5] Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better lattice security estimates (full version) (2011). http://www.di.ens.fr/ ychen/research/Full_BKZ.pdf · Zbl 1227.94037
[6] Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal Gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 40–56. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-40041-4_3 · Zbl 1310.94141 · doi:10.1007/978-3-642-40041-4_3
[7] Fluhrer, S.R.: Quantum cryptanalysis of NTRU. IACR Cryptology ePrint Archive, 2015:676 (2015)
[8] Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008). doi: 10.1007/978-3-540-78967-3_3 · Zbl 1149.94314 · doi:10.1007/978-3-540-78967-3_3
[9] Hirschhorn, P.S., Hoffstein, J., Howgrave-Graham, N., Whyte, W.: Choosing NTRUEncrypt parameters in light of combined lattice reduction and MITM approaches. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 437–455. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-01957-9_27 · Zbl 05561271 · doi:10.1007/978-3-642-01957-9_27
[10] Hoffstein, J., Pipher, J., Schanck, J.M., Silverman, J.H., Whyte, W., Zhang, Z.: Choosing Parameters for NTRUEncrypt (full version). IACR Cryptology ePrint Archive 2015:708 (2015) · Zbl 1383.94022
[11] Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998). doi: 10.1007/BFb0054868 · Zbl 1067.94538 · doi:10.1007/BFb0054868
[12] Hoffstein, J., Silverman, J.H.: Optimizations for NTRU (2000) · Zbl 0987.94027
[13] Hoffstein, J., Silverman, J.H.: Random small hamming weight products with applications to cryptography. Discrete Appl. Math. 130(1), 37–49 (2003) · Zbl 1028.94023 · doi:10.1016/S0166-218X(02)00588-7
[14] Hoffstein, J., Silverman, J.H., Whyte, W.: Provable Probability Bounds for NTRUEncrypt Convolution (2007). http://www.ntru.com
[15] Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150–169. Springer, Heidelberg (2007). doi: 10.1007/978-3-540-74143-5_9 · Zbl 1215.94053 · doi:10.1007/978-3-540-74143-5_9
[16] Howgrave-Graham, N., Silverman, J.H., Whyte, W.: Choosing parameter sets for NTRUEncrypt with NAEP and SVES-3. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 118–135. Springer, Heidelberg (2005). doi: 10.1007/978-3-540-30574-3_10 · Zbl 1079.94553 · doi:10.1007/978-3-540-30574-3_10
[17] Stehlé, D., Steinfeld, R.: Making NTRU as secure as worst-case problems over ideal lattices. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 27–47. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-20465-4_4 · Zbl 1281.94057 · doi:10.1007/978-3-642-20465-4_4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.