×

zbMATH — the first resource for mathematics

A detailed analysis of the hybrid lattice-reduction and meet-in-the-middle attack. (English) Zbl 1415.94466
Summary: Over the past decade, the hybrid lattice-reduction and meet-in-the middle attack (called hybrid attack) has been used to evaluate the security of many lattice-based cryptographic schemes such as NTRU, NTRU Prime, BLISS and more. However, unfortunately, none of the previous analyses of the hybrid attack is entirely satisfactory: They are based on simplifying assumptions that may distort the security estimates. Such simplifying assumptions include setting probabilities equal to 1, which, for the parameter sets we analyze in this work, are in fact as small as \(2^{-80}\). Many of these assumptions lead to underestimating the scheme’s security. However, some lead to security overestimates, and without further analysis, it is not clear which is the case. Therefore, the current security estimates against the hybrid attack are not reliable, and the actual security levels of many lattice-based schemes are unclear. In this work, we present an improved runtime analysis of the hybrid attack that is based on more reasonable assumptions. In addition, we reevaluate the security against the hybrid attack for the NTRU, NTRU Prime and R-BinLWEEnc encryption schemes as well as for the BLISS and GLP signature schemes. Our results show that there exist both security over- and underestimates in the literature.

MSC:
94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
Software:
SageMath; BLISS; NTRU; BKZ; DLMF
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. R. Albrecht, R. Fitzpatrick and F. Göpfert, On the efficacy of solving LWE by reduction to unique-SVP, Information Security and Cryptology—ICISC 2013, Lecture Notes in Comput. Sci. 8565, Springer, Cham (2014), 293-310. · Zbl 1368.94082
[2] M. R. Albrecht, R. Player and S. Scott, On the concrete hardness of learning with errors, J. Math. Cryptol. 9 (2015), no. 3, 169-203. · Zbl 1352.94023
[3] E. Alkim, L. Ducas, T. Pöppelmann and P. Schwabe, Post-quantum key exchange - A new hope, Proceedings of the 25th USENIX Security Symposium, USENIX, Berkeley (2016), 327-343.
[4] Y. Aono, Y. Wang, T. Hayashi and T. Takagi, Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator, Advances in Cryptology—EUROCRYPT 2016. Part I, Lecture Notes in Comput. Sci. 9665, Springer, Berlin (2016), 789-819. · Zbl 1385.94007
[5] L. Babai, On Lovász’ lattice reduction and the nearest lattice point problem, Annual Symposium on Theoretical Aspects of Computer Science—STACS 85, Lecture Notes in Comput. Sci. 182, Springer, Berlin, (1985) 13-20. · Zbl 0593.68030
[6] S. Bai and S. D. Galbraith, Lattice decoding attacks on binary LWE, Information Security and Privacy—ACISP 2014, Lecture Notes in Comput. Sci. 8544, Springer, Berlin (2014), 322-337. · Zbl 1337.94020
[7] D. J. Bernstein, J. Buchmann and E. Dahmen, Post-Quantum Cryptography, Springer, Berlin, 2009.
[8] D. J. Bernstein, C. Chuengsatiansup, T. Lange and C. van Vredendaal, NTRU prime: Reducing attack surface at low cost, Selected Areas in Cryptography—SAC 2017, Lecture Notes in Comput. Sci. 10719, Springer, Cham (2018), 235-260. · Zbl 1384.94034
[9] J. Buchmann, F. Göpfert, T. Güneysu, T. Oder and T. Pöppelmann, High-performance and lightweight lattice-based public-key encryption, Proceedings of the 2nd ACM International Workshop on IoT Privacy, Trust, and Security, ACM, New York (2016), 2-9.
[10] J. Buchmann, F. Göpfert, R. Player and T. Wunderer, On the hardness of LWE with binary error: Revisiting the hybrid lattice-reduction and meet-in-the-middle attack, Progress in Cryptology—AFRICACRYPT 2016, Lecture Notes in Comput. Sci. 9646, Springer, Cham (2016), 24-43. · Zbl 1345.94045
[11] R. Canetti and J. A. Garay, Advances in Cryptology—CRYPTO 2013. Part I, Lecture Notes in Comput. Sci. 8042, Springer, Heidelberg, 2013. · Zbl 1270.94007
[12] Y. Chen, Réduction de réseau et sécurité concrete du chiffrement completement homomorphe, PhD thesis, Paris 7, 2013.
[13] Y. Chen and P. Q. Nguyen, BKZ 2.0: Better lattice security estimates, Advances in Cryptology—ASIACRYPT 2011, Lecture Notes in Comput. Sci. 7073, Springer, Heidelberg (2011), 1-20. · Zbl 1227.94037
[14] L. Ducas, A. Durmus, T. Lepoint and V. Lyubashevsky, Lattice signatures and bimodal Gaussians, Advances in Cryptology—CRYPTO 2013. Part I, Lecture Notes in Comput. Sci. 8042, Springer, Heidelberg (2013), 40-56. · Zbl 1310.94141
[15] M. Fischlin and J.-S. Coron, Advances in Cryptology—EUROCRYPT 2016. Part I, Lecture Notes in Comput. Sci. 9665, Springer, Berlin, 2016.
[16] T. Güneysu, V. Lyubashevsky and T. Pöppelmann, Practical lattice-based cryptography: A signature scheme for embedded systems, Cryptographic Hardware and Embedded Systems—CHES 2012, Lecture Notes in Comput. Sci. 7428, Springer, Berlin (2012), 530-547. · Zbl 1294.94050
[17] P. S. Hirschhorn, J. Hoffstein, N. Howgrave-Graham and W. Whyte, Choosing NTRUencrypt parameters in light of combined lattice reduction and MITM approaches, Applied Cryptography and Network Security—ACNS 2009, Lecture Notes in Comput. Sci. 5536, Springer, Berlin (2009), 437-455.
[18] J. Hoffstein, J. Pipher, J. M. Schanck, J. H. Silverman, W. Whyte and Z. Zhang, Choosing parameters for {NTRUEncrypt}, Topics in Cryptology—CT-RSA 2017, Lecture Notes in Comput. Sci. 10159, Springer, Cham (2017), 3-18. · Zbl 1383.94022
[19] J. Hoffstein, J. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, Algorithmic Number Theory (Portland 1998), Lecture Notes in Comput. Sci. 1423, Springer, Berlin (1998), 267-288. · Zbl 1067.94538
[20] N. Howgrave-Graham, A hybrid lattice-reduction and meet-in-the-middle attack against NTRU, Advances in Cryptology—CRYPTO 2007, Lecture Notes in Comput. Sci. 4622, Springer, Berlin (2007), 150-169. · Zbl 1215.94053
[21] N. Howgrave-Graham, A hybrid lattice-reduction and meet-in-the-middle attack against NTRU, Advances in Cryptology—CRYPTO 2007, Lecture Notes in Comput. Sci. 4622, Springer, Berlin (2007), 150-169. · Zbl 1215.94053
[22] N. Howgrave-Graham, J. H. Silverman and W. Whyte, A meet-in-the-middle attack on an NTRU private key, .
[23] A. K. Lenstra and E. R. Verheul, Selecting cryptographic key sizes, J. Cryptology 14 (2001), no. 4, 255-293. · Zbl 1006.94020
[24] R. Lindner and C. Peikert, Better key sizes (and attacks) for LWE-based encryption, Topics in Cryptology—CT-RSA 2011, Lecture Notes in Comput. Sci. 6558, Springer, Heidelberg (2011), 319-339. · Zbl 1284.94088
[25] V. Lyubashevsky, C. Peikert and O. Regev, On ideal lattices and learning with errors over rings, J. ACM 60 (2013), no. 6, Article ID 43. · Zbl 1281.68140
[26] D. Micciancio and C. Peikert, Hardness of SIS and LWE with small parameters, Advances in Cryptology—CRYPTO 2013. Part I, Lecture Notes in Comput. Sci. 8042, Springer, Heidelberg (2013), 21-39. · Zbl 1310.94161
[27] D. Micciancio and M. Walter, Practical, predictable lattice basis reduction, Advances in Cryptology—EUROCRYPT 2016. Part I, Lecture Notes in Comput. Sci. 9665, Springer, Berlin (2016), 820-849. · Zbl 1385.94062
[28] F. W. J. Olver, NIST Handbook Of Mathematical Functions, Cambridge University Press, Cambridge, 2010. · Zbl 1198.00002
[29] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the 37th Annual ACM Symposium on Theory of Computing—STOC’05, ACM, New York (2005), 84-93. · Zbl 1192.94106
[30] J. Schanck, Practical lattice cryptosystems: NTRUEncrypt and NTRUMLS, Master’s thesis, University of Waterloo, 2015.
[31] W. Stein, Sage Mathematics Software Version 7.5.1, The Sage Development Team 2017, .
[32] C. van Vredendaal, Reduced memory meet-in-the-middle attack against the NTRU private key, LMS J. Comput. Math. 19 (2016), no. Suppl. A, 43-57. · Zbl 1391.94827
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.