zbMATH — the first resource for mathematics

Estimation of the hardness of the learning with errors problem with a restricted number of samples. (English) Zbl 1458.94214
Summary: The Learning With Errors (LWE) problem is one of the most important hardness assumptions lattice-based constructions base their security on. In 2015, Albrecht, Player and Scott [M. R. Albrecht et al., J. Math. Cryptol. 9, No. 3, 169–203 (2015; Zbl 1352.94023)] presented the software tool LWE-Estimator to estimate the hardness of concrete LWE instances, making the choice of parameters for lattice-based primitives easier and better comparable. To give lower bounds on the hardness, it is assumed that each algorithm has given the corresponding optimal number of samples. However, this is not the case for many cryptographic applications. In this work we first analyze the hardness of LWE instances given a restricted number of samples. For this, we describe LWE solvers from the literature and estimate their runtime considering a limited number of samples. Based on our theoretical results we extend the LWE-Estimator. Furthermore, we evaluate LWE instances proposed for cryptographic schemes and show the impact of restricting the number of available samples.
94A60 Cryptography
Full Text: DOI
[1] M. R. Albrecht, C. Cid, J.-C. Faugère, R. Fitzpatrick and L. Perret, On the complexity of the BKW algorithm on LWE, Des. Codes Cryptogr. 74 (2015), no. 2, 325-354. · Zbl 1331.94051
[2] 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, Berlin (2014), 293-310. · Zbl 1368.94082
[3] M. R. Albrecht, F. Göpfert, C. Lefebvre, R. Player and S. Scott, Estimator for the bit security of LWE instances, 2016, [Online; accessed 01-June-2017].
[4] 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
[5] E. Alkim, N. Bindel, J. Buchmann, O. Dagdelen, E. Eaton, G. Gutoski, J. Krämer and F. Pawlega, Revisiting TESLA in the quantum random oracle model, Post-Quantum Cryptography, Lecture Notes in Comput. Sci. 10346, Springer, Berlin (2017), 143-162. · Zbl 1437.94047
[6] E. Alkim, L. Ducas, T. Pöppelmann and P. Schwabe, Post-quantum key exchange - A new hope, Proceedings of the 25th USENIX Security Symposium (Austin 2016), USENIX, Berkeley (2016), 327-343.
[7] B. Applebaum, D. Cash, C. Peikert and A. Sahai, Fast cryptographic primitives and circular-secure encryption based on hard learning problems, Advances in Cryptology - CRYPTO 2009, Lecture Notes in Comput. Sci. 5677, Springer, Berlin (2009), 595-618. · Zbl 1252.94044
[8] S. Arora and R. Ge, New algorithms for learning in presence of errors, Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci. 6755, Springer, Berlin (2011), 403-415. · Zbl 1332.68099
[9] L. Babai, On Lovász’ lattice reduction and the nearest lattice point problem, STACS 85 (Saarbrücken 1985), Lecture Notes in Comput. Sci. 182, Springer, Berlin (1985), 13-20. · Zbl 0593.68030
[10] S. Bai and S. D. Galbraith, An improved compression technique for signatures based on learning with errors, Topics in Cryptology - CT-RSA 2014, Lecture Notes in Comput. Sci. 8366, Springer, Berlin (2014), 28-47. · Zbl 1295.94011
[11] A. Becker, L. Ducas, N. Gama and T. Laarhoven, New directions in nearest neighbor searching with applications to lattice sieving, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York (2016), 10-24. · Zbl 1410.68093
[12] J. Bos, C. Costello, L. Ducas, I. Mironov, M. Naehrig, V. Nikolaenko, A. Raghunathan and D. Stebila, Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, ACM, New York (2016), 1006-1018.
[13] J. Bos, C. Costello, M. Naehrig and D. Stebila, Post-quantum key exchange for the TLS protocol from the ring learning with errors problem, IEEE Symposium on Security and Privacy, IEEE Press, Piscataway (2015), 553-570.
[14] 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, Berlin (2011), 1-20. · Zbl 1227.94037
[15] H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952), 493-507. · Zbl 0048.11804
[16] Ö. Dagdelen, R. El Bansarkhani, F. Göpfert, T. Güneysu, T. Oder, T. Pöppelmann, A. H. Sánchez and P. Schwabe, High-speed signatures from standard lattices, Progress in Cryptology - LATINCRYPT 2014, Lecture Notes in Comput. Sci. 8895, Springer, Berlin (2015), 84-103. · Zbl 1378.94034
[17] A. Duc, F. Tramèr and S. Vaudenay, Better algorithms for LWE and LWR, Advances in Cryptology - EUROCRYPT 2015. Part I, Lecture Notes in Comput. Sci. 9056, Springer, Berlin (2015), 173-202. · Zbl 1365.94424
[18] R. El Bansarkhani, Lara - A design concept for lattice-based encryption, preprint (2017), .
[19] N. Gama, P. Q. Nguyen and O. Regev, Lattice enumeration using extreme pruning, Advances in Cryptology - EUROCRYPT 2010, Lecture Notes in Comput. Sci. 6110, Springer, Berlin (2010), 257-278. · Zbl 1280.94056
[20] C. Gentry, C. Peikert and V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing - STOC’08, ACM, New York (2008), 197-206. · Zbl 1231.68124
[21] F. Göpfert, Securely instantiating cryptographic schemes based on the learning with errors assumption, PhD thesis, Darmstadt University of Technology, Darmstadt, 2016.
[22] G. Hanrot, X. Pujol and D. Stehlé, Algorithms for the shortest and closest lattice vector problems, Coding and Cryptology, Lecture Notes in Comput. Sci. 6639, Springer, Berlin (2011), 159-190. · Zbl 1272.68477
[23] T. Laarhoven, M. Mosca and J. van de Pol, Finding shortest lattice vectors faster using quantum search, Des. Codes Cryptogr. 77 (2015), no. 2-3, 375-400. · Zbl 1356.94069
[24] A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515-534. · Zbl 0488.12001
[25] H. W. Lenstra, Jr., Integer programming with a fixed number of variables, Math. Oper. Res. 8 (1983), no. 4, 538-548. · Zbl 0524.90067
[26] 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, Berlin (2011), 319-339. · Zbl 1284.94088
[27] V. Lyubashevsky and D. Micciancio, On bounded distance decoding, unique shortest vectors, and the minimum distance problem, Advances in Cryptology - CRYPTO 2009, Lecture Notes in Comput. Sci. 5677, Springer, Berlin (2009), 577-594. · Zbl 1252.94084
[28] D. Micciancio and O. Regev, Lattice-based cryptography, Post-Quantum Cryptography, Springer, Berlin (2009), 147-191. · Zbl 1161.81324
[29] P. Q. Nguyên and D. Stehlé, Floating-point LLL revisited, Advances in Cryptology - EUROCRYPT 2005, Lecture Notes in Comput. Sci. 3494, Springer, Berlin (2005), 215-233. · Zbl 1137.94353
[30] C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem: extended abstract, Proceedings of the 2009 ACM International Symposium on Theory of Computing - STOC’09, ACM, New York (2009), 333-342. · Zbl 1304.94079
[31] 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
[32] C.-P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program. 66 (1994), no. 2, 181-199. · Zbl 0829.90099
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.