×

Characterizing overstretched NTRU attacks. (English) Zbl 1448.94241

Summary: Overstretched NTRU is a variant of NTRU with a large modulus. Recent lattice subfield and subring attacks have broken suggested parameters for several schemes. There are a number of conflicting claims in the literature over which attack has the best performance. These claims are typically based on experiments more than analysis. In this paper, we argue that comparisons should focus on the lattice dimension used in the attack. We give evidence, both analytically and experimentally, that the subring attack finds shorter vectors and thus is expected to succeed with a smaller dimension lattice than the subfield attack for the same problem parameters, and also to succeed with a smaller modulus when the lattice dimension is fixed.

MSC:

94A62 Authentication, digital signatures and secret sharing
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94A60 Cryptography

Software:

NTRU; NTRUSign
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Albrecht, S. Bai, and L. Ducas. A Subfield Lattice Attack on Overstretched NTRU Assumptions. CRYPTO 2016. · Zbl 1351.94019
[2] W.D. Banks and I.E. Shparlinski. Distribution of Inverses in Polynomial Rings. Indagationes Mathematicae, 12(3), 2001. · Zbl 1095.13534
[3] D. Boneh and R. Venkatesan. Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes. CRYPTO 1996. · Zbl 1329.94054
[4] J. H. Cheon, J. Jeong, and C. Lee. An Algorithm for NTRU Problems and Cryptanalysis of the GGH Multilinear Map without a Low-Level Encoding of Zero. LMS Journal of Computation and Mathematics, 19(A): 2016. · Zbl 1404.94053
[5] D. Coppersmith and A. Shamir. Lattice Attacks on NTRU. Eurocrypt ’97.
[6] G. De Micheli, N. Heninger, and B. Shani. Characterizing overstretched NTRU attacks. ePrint 2018/630
[7] M. Drmota and R. Tichy. Discrepancies and Applications.
[8] D. H. Duong, M. Yasuda, and T. Takagi. Choosing Parameters for the Subfield Lattice Attack Against Overstretched NTRU. Information Security 2017.
[9] S. Garg, C. Gentry, and S. Halevi. Candidate Multilinear Maps from Ideal Lattices. EUROCRYPT 2013. · Zbl 1300.94055
[10] J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte. NTRUSign: Digital Signatures Using the NTRU Lattice. CT-RSA 2003. · Zbl 1039.94525
[11] J. Hoffstein, J. Pipher, and J. H. Silverman. NTRU: A Ring-based Public Key Cryptosystem. Algorithmic Number Theory 1998. · Zbl 1067.94538
[12] P. Kirchner and P.-A. Fouque. Revisiting Lattice Attacks on Overstretched NTRU Parameters. EUROCRYPT 2017. · Zbl 1410.94084
[13] R. Kuipers and H. Niederreiter. Uniform Distribution of Sequences. · Zbl 0568.10001
[14] A. López-Alt, E. Tromer, and V. Vaikuntanathan. On-the-fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption. STOC ’12. · Zbl 1286.68114
[15] G. F. Lawler and V. Limic. Random Walk: A Modern Introduction. · Zbl 1210.60002
[16] R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, 1997.
[17] A. May. Cryptanalysis of NTRU, 1999.
[18] A. May and J. H. Silverman. Dimension Reduction Methods for Convolution Modular Lattices. Cryptography and Lattices. · Zbl 1006.11033
[19] G. Pataki and M. Tural. On Sublattice Determinants in Reduced Bases, 2008.
[20] P. Samuel. Algebraic Theory of Numbers. Hermann, 1970. · Zbl 0215.36001
[21] C. P. Schnorr. A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms. Theor. Comput. Sci., 53(2-3):201-224, August 1987. · Zbl 0642.10030
[22] D. Stehlé and R. Steinfeld. Making NTRU as Secure as Worst-Case Problems over Ideal Lattices. EUROCRYPT 2011. · Zbl 1281.94057
[23] R. Steinfeld. NTRU Cryptosystem: Recent Developments and Emerging Mathematical Problems in Finite Polynomial Rings. Walter de Gruyter, 2014.
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.