{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T23:02:37Z","timestamp":1648940557779},"reference-count":64,"publisher":"Walter de Gruyter GmbH","issue":"1","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["CRC 1119 CROSSING"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,3,1]]},"abstract":"Abstract<\/jats:title>\n The Learning With Errors (LWE) problem is one of the most important hardness\nassumptions lattice-based constructions base their security on. In 2015,\nAlbrecht, Player and Scott presented the\nsoftware tool LWE-Estimator<\/jats:italic> to estimate the hardness of concrete LWE\ninstances, making the choice of parameters for lattice-based primitives easier\nand better comparable.\nTo give lower bounds on the hardness, it is assumed that\neach algorithm has given the corresponding optimal number of samples. However,\nthis is not the case for many cryptographic applications.\nIn this work\nwe first analyze the hardness of LWE instances given a restricted number of\nsamples. For this, we describe LWE solvers from the literature and estimate\ntheir runtime considering a limited number of samples.\nBased on our theoretical results we extend the LWE-Estimator.\nFurthermore, we evaluate LWE instances proposed for cryptographic schemes\nand show the impact of restricting the number of available samples.<\/jats:p>","DOI":"10.1515\/jmc-2017-0040","type":"journal-article","created":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T07:23:41Z","timestamp":1533799421000},"page":"47-67","source":"Crossref","is-referenced-by-count":1,"title":["Estimation of the hardness of the learning with errors problem with a restricted number of samples"],"prefix":"10.1515","volume":"13","author":[{"given":"Nina","family":"Bindel","sequence":"first","affiliation":[]},{"given":"Johannes","family":"Buchmann","sequence":"additional","affiliation":[]},{"given":"Florian","family":"G\u00f6pfert","sequence":"additional","affiliation":[]},{"given":"Markus","family":"Schmidt","sequence":"additional","affiliation":[]}],"member":"374","reference":[{"key":"ref601","first-page":"215","article-title":"Floating-point LLL revisited","year":"2005","journal-title":"Advances in Cryptology \u2013 EUROCRYPT 2005"},{"key":"ref21","article-title":"Estimator for the bit security of LWE instances","journal-title":"Preprint"},{"key":"ref191","first-page":"197","article-title":"Trapdoors for hard lattices and new cryptographic constructions","year":"2008","journal-title":"Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing \u2013 STOC\u201908"},{"key":"ref501","first-page":"257","article-title":"Lattice enumeration using extreme pruning","year":"2010","journal-title":"Advances in Cryptology \u2013 EUROCRYPT 2010"},{"key":"ref531","first-page":"159","article-title":"Algorithms for the shortest and closest lattice vector problems","year":"2011","journal-title":"Coding and Cryptology"},{"key":"ref551","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","year":"1982","journal-title":"Math. Ann."},{"key":"ref561","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","article-title":"Integer programming with a fixed number of variables","volume":"8","year":"1983","journal-title":"Math. Oper. Res."},{"key":"ref451","first-page":"1","article-title":"BKZ 2.0: Better lattice security estimates","year":"2011","journal-title":"Advances in Cryptology \u2013 ASIACRYPT 2011"},{"key":"ref161","first-page":"173","article-title":"Better algorithms for LWE and LWR","year":"2015","journal-title":"Advances in Cryptology \u2013 EUROCRYPT 2015. Part I"},{"key":"ref321","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s10623-013-9864-x","article-title":"On the complexity of the BKW algorithm on LWE","volume":"74","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref41","first-page":"143","article-title":"Revisiting TESLA in the quantum random oracle model","year":"2017","journal-title":"Post-Quantum Cryptography"},{"key":"ref181","first-page":"257","article-title":"Lattice enumeration using extreme pruning","year":"2010","journal-title":"Advances in Cryptology \u2013 EUROCRYPT 2010"},{"key":"ref131","first-page":"1","article-title":"BKZ 2.0: Better lattice security estimates","year":"2011","journal-title":"Advances in Cryptology \u2013 ASIACRYPT 2011"},{"key":"ref201","year":"2016","journal-title":"Securely instantiating cryptographic schemes based on the learning with errors assumption"},{"key":"ref261","first-page":"577","article-title":"On bounded distance decoding, unique shortest vectors, and the minimum distance problem","year":"2009","journal-title":"Advances in Cryptology \u2013 CRYPTO 2009"},{"key":"ref471","first-page":"84","article-title":"High-speed signatures from standard lattices","year":"2015","journal-title":"Progress in Cryptology \u2013 LATINCRYPT 2014"},{"key":"ref401","first-page":"13","article-title":"On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem","year":"1985","journal-title":"STACS 85"},{"key":"ref11","first-page":"293","article-title":"On the efficacy of solving LWE by reduction to unique-SVP","year":"2014","journal-title":"Information Security and Cryptology \u2013 ICISC 2013"},{"key":"ref481","first-page":"173","article-title":"Better algorithms for LWE and LWR","year":"2015","journal-title":"Advances in Cryptology \u2013 EUROCRYPT 2015. Part I"},{"key":"ref441","first-page":"553","article-title":"Post-quantum key exchange for the TLS protocol from the ring learning with errors problem","year":"2015","journal-title":"IEEE Symposium on Security and Privacy"},{"key":"ref31","first-page":"169","article-title":"On the concrete hardness of learning with errors","volume":"9","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref421","first-page":"10","article-title":"New directions in nearest neighbor searching with applications to lattice sieving","year":"2016","journal-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"ref491","article-title":"Lara \u2013 A design concept for lattice-based encryption","year":"2017","journal-title":"Preprint"},{"key":"ref71","first-page":"403","article-title":"New algorithms for learning in presence of errors","year":"2011","journal-title":"Automata, Languages and Programming. Part I"},{"key":"ref361","first-page":"143","article-title":"Revisiting TESLA in the quantum random oracle model","year":"2017","journal-title":"Post-Quantum Cryptography"},{"key":"ref251","first-page":"319","article-title":"Better key sizes (and attacks) for LWE-based encryption","year":"2011","journal-title":"Topics in Cryptology \u2013 CT-RSA 2011"},{"key":"ref591","first-page":"147","article-title":"Lattice-based cryptography","year":"2009","journal-title":"Post-Quantum Cryptography"},{"key":"ref331","first-page":"293","article-title":"On the efficacy of solving LWE by reduction to unique-SVP","year":"2014","journal-title":"Information Security and Cryptology \u2013 ICISC 2013"},{"key":"ref101","first-page":"10","article-title":"New directions in nearest neighbor searching with applications to lattice sieving","year":"2016","journal-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"ref411","first-page":"28","article-title":"An improved compression technique for signatures based on learning with errors","year":"2014","journal-title":"Topics in Cryptology \u2013 CT-RSA 2014"},{"key":"ref461","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations","volume":"23","year":"1952","journal-title":"Ann. Math. Statistics"},{"key":"ref141","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations","volume":"23","year":"1952","journal-title":"Ann. Math. Statistics"},{"key":"ref241","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","article-title":"Integer programming with a fixed number of variables","volume":"8","year":"1983","journal-title":"Math. Oper. Res."},{"key":"ref581","first-page":"577","article-title":"On bounded distance decoding, unique shortest vectors, and the minimum distance problem","year":"2009","journal-title":"Advances in Cryptology \u2013 CRYPTO 2009"},{"key":"ref311","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice basis reduction: Improved practical algorithms and solving subset sum problems","volume":"66","year":"1994","journal-title":"Math. Program."},{"key":"ref51","first-page":"327","article-title":"Post-quantum key exchange \u2013 A new hope","year":"2016","journal-title":"Proceedings of the 25th USENIX Security Symposium"},{"key":"ref541","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s10623-015-0067-5","article-title":"Finding shortest lattice vectors faster using quantum search","volume":"77","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref171","article-title":"Lara \u2013 A design concept for lattice-based encryption","year":"2017","journal-title":"Preprint"},{"key":"ref01","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s10623-013-9864-x","article-title":"On the complexity of the BKW algorithm on LWE","volume":"74","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref301","first-page":"84","article-title":"On lattices, learning with errors, random linear codes, and cryptography","year":"2005","journal-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing \u2013 STOC\u201905"},{"key":"ref151","first-page":"84","article-title":"High-speed signatures from standard lattices","year":"2015","journal-title":"Progress in Cryptology \u2013 LATINCRYPT 2014"},{"key":"ref281","first-page":"215","article-title":"Floating-point LLL revisited","year":"2005","journal-title":"Advances in Cryptology \u2013 EUROCRYPT 2005"},{"key":"ref371","first-page":"327","article-title":"Post-quantum key exchange \u2013 A new hope","year":"2016","journal-title":"Proceedings of the 25th USENIX Security Symposium"},{"key":"ref381","first-page":"595","article-title":"Fast cryptographic primitives and circular-secure encryption based on hard learning problems","year":"2009","journal-title":"Advances in Cryptology \u2013 CRYPTO 2009"},{"key":"ref521","year":"2016","journal-title":"Securely instantiating cryptographic schemes based on the learning with errors assumption"},{"key":"ref611","first-page":"333","article-title":"Public-key cryptosystems from the worst-case shortest vector problem: extended abstract","year":"2009","journal-title":"Proceedings of the 2009 ACM International Symposium on Theory of Computing \u2013 STOC\u201909"},{"key":"ref111","first-page":"1006","article-title":"Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE","year":"2016","journal-title":"Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security"},{"key":"ref351","first-page":"169","article-title":"On the concrete hardness of learning with errors","volume":"9","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref271","first-page":"147","article-title":"Lattice-based cryptography","year":"2009","journal-title":"Post-Quantum Cryptography"},{"key":"ref431","first-page":"1006","article-title":"Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE","year":"2016","journal-title":"Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security"},{"key":"ref121","first-page":"553","article-title":"Post-quantum key exchange for the TLS protocol from the ring learning with errors problem","year":"2015","journal-title":"IEEE Symposium on Security and Privacy"},{"key":"ref621","first-page":"84","article-title":"On lattices, learning with errors, random linear codes, and cryptography","year":"2005","journal-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing \u2013 STOC\u201905"},{"key":"ref571","first-page":"319","article-title":"Better key sizes (and attacks) for LWE-based encryption","year":"2011","journal-title":"Topics in Cryptology \u2013 CT-RSA 2011"},{"key":"ref81","first-page":"13","article-title":"On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem","year":"1985","journal-title":"STACS 85"},{"key":"ref631","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice basis reduction: Improved practical algorithms and solving subset sum problems","volume":"66","year":"1994","journal-title":"Math. Program."},{"key":"ref91","first-page":"28","article-title":"An improved compression technique for signatures based on learning with errors","year":"2014","journal-title":"Topics in Cryptology \u2013 CT-RSA 2014"},{"key":"ref211","first-page":"159","article-title":"Algorithms for the shortest and closest lattice vector problems","year":"2011","journal-title":"Coding and Cryptology"},{"key":"ref291","first-page":"333","article-title":"Public-key cryptosystems from the worst-case shortest vector problem: extended abstract","year":"2009","journal-title":"Proceedings of the 2009 ACM International Symposium on Theory of Computing \u2013 STOC\u201909"},{"key":"ref341","article-title":"Estimator for the bit security of LWE instances","journal-title":"Preprint"},{"key":"ref391","first-page":"403","article-title":"New algorithms for learning in presence of errors","year":"2011","journal-title":"Automata, Languages and Programming. Part I"},{"key":"ref61","first-page":"595","article-title":"Fast cryptographic primitives and circular-secure encryption based on hard learning problems","year":"2009","journal-title":"Advances in Cryptology \u2013 CRYPTO 2009"},{"key":"ref221","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s10623-015-0067-5","article-title":"Finding shortest lattice vectors faster using quantum search","volume":"77","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref231","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","year":"1982","journal-title":"Math. Ann."},{"key":"ref511","first-page":"197","article-title":"Trapdoors for hard lattices and new cryptographic constructions","year":"2008","journal-title":"Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing \u2013 STOC\u201908"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/jmc.2019.13.issue-1\/jmc-2017-0040\/jmc-2017-0040.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2017-0040\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,22]],"date-time":"2021-04-22T01:17:25Z","timestamp":1619054245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2017-0040\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,1]]},"references-count":64,"journal-issue":{"issue":"1"},"URL":"http:\/\/dx.doi.org\/10.1515\/jmc-2017-0040","relation":{},"ISSN":["1862-2976","1862-2984"],"issn-type":[{"value":"1862-2976","type":"print"},{"value":"1862-2984","type":"electronic"}],"subject":["Applied Mathematics","Computational Mathematics","Computer Science Applications"],"published":{"date-parts":[[2019,3,1]]}}}