{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T08:27:53Z","timestamp":1774772873682,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,7,19]],"date-time":"2013-07-19T00:00:00Z","timestamp":1374192000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2015,2]]},"DOI":"10.1007\/s10623-013-9864-x","type":"journal-article","created":{"date-parts":[[2013,7,18]],"date-time":"2013-07-18T10:29:21Z","timestamp":1374143361000},"page":"325-354","source":"Crossref","is-referenced-by-count":69,"title":["On the complexity of the BKW algorithm on LWE"],"prefix":"10.1007","volume":"74","author":[{"given":"Martin R.","family":"Albrecht","sequence":"first","affiliation":[]},{"given":"Carlos","family":"Cid","sequence":"additional","affiliation":[]},{"given":"Jean-Charles","family":"Faug\u00e8re","sequence":"additional","affiliation":[]},{"given":"Robert","family":"Fitzpatrick","sequence":"additional","affiliation":[]},{"given":"Ludovic","family":"Perret","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,7,19]]},"reference":[{"key":"9864_CR1","unstructured":"Agrawal S., Gentry C., Halevi S., Sahai A.: Discrete Gaussian Leftover Hash Lemma over infinite domains. Cryptology ePrint Archive, Report 2012\/714, http:\/\/eprint.iacr.org\/ (2012). Accessed 27 Dec 2012."},{"key":"9864_CR2","unstructured":"Ajtai M., Kumar R., Sivakumar, D.: Sampling short lattice vectors and the closest lattice vector problem. In: IEEE Conference on Computational Complexity, pp. 53\u201357 (2002)."},{"key":"9864_CR3","unstructured":"Albrecht M.R.: https:\/\/bitbucket.org\/malb\/research-snippets\/ (2012). Accessed 30 June 2013."},{"key":"9864_CR4","unstructured":"Albrecht M.R., Farshim P., Faug\u00e8re J-.C., Perret L.: Polly Cracker, revisited. In: Advances in Cryptology\u2014ASIACRYPT 2011. Lecture Notes in Computer Science, vol. 7073, pp. 179\u2013196. Springer, Berlin. Cryptology ePrint Archive, Report 2011\/289, http:\/\/eprint.iacr.org\/ (2011). Accessed 19 Nov 2012."},{"key":"9864_CR5","unstructured":"Albrecht M., Cid C., Faug\u00e8re J-.C., Fitzpatrick R., Perret L.: On the complexity of the Arora\u2013Ge algorithm against LWE. In: Faug\u00e8re J-.C., Gomez D., Gutierrez J., Perret L. (eds.) SCC \u201912: Proceedings of the 3nd International Conference on Symbolic Computation and Cryptography, pp. 93\u201399. Castro-Urdiales, July (2012)."},{"key":"9864_CR6","unstructured":"Albrecht M.R., Fitzpatrick R., Cabracas D., G\u00f6pfert F., Schneider M.: A generator for LWE and Ring-LWE instances. http:\/\/www.iacr.org\/news\/files\/2013-04-29lwe-generator.pdf (2013). Accessed 29 Apr 2013."},{"key":"9864_CR7","unstructured":"Arora S.. Ge R.: New algorithms for learning in presence of errors. In: Aceto L., Henzinger M., Sgall J. (eds.) ICALP. Lecture Notes in Computer Science, vol. 6755, pp. 403\u2013415. Springer, Berlin (2011)."},{"key":"9864_CR8","unstructured":"Baigneres T., Junod P., Vaudenay S.: How far can we go beyond linear cryptanalysis? In: Lee P.J. (ed.) Advances in Cryptology\u2014ASIACRYPT 2004. Lecture Notes in Computer Science, vol. 3329, pp. 432\u2013450, Springer, Berlin (2004)."},{"key":"9864_CR9","doi-asserted-by":"crossref","unstructured":"Blum A., Kalai A., Wasserman H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM. 50(4), 506\u2013519 (2003).","DOI":"10.1145\/792538.792543"},{"key":"9864_CR10","unstructured":"Brakerski Z., Vaikuntanathan V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 97\u2013106. IEEE (2011)."},{"key":"9864_CR11","doi-asserted-by":"crossref","unstructured":"Brakerski Z., Langlois A., Peikert C., Regev O., Stehl\u00e9 D.: Classical hardness of learning with errors. STOC. (2013) (to appear).","DOI":"10.1145\/2488608.2488680"},{"key":"9864_CR12","unstructured":"Chen Y., Nguyen P.Q.: BKZ 2.0: better lattice security estimates. In: Lee D.H., Wang X. (eds.) Advances in Cryptology\u2014ASIACRYPT 2011. Lecture Notes in Computer Science, vol. 7073, pp. 1\u201320, Springer, Berlin (2011)."},{"key":"9864_CR13","unstructured":"Duembgen L.: Bounding standard gaussian tail probabilities. arXiv:1012.2063 (2010)."},{"key":"9864_CR14","unstructured":"Fouque P-.A., Levieil \u00c9.: An improved LPN algorithm. In: De Prisco R., Yung M. (eds.) Security and Cryptography for Networks, 5th International Conference, SCN 2006. Lecture Notes in Computer Science, vol. 4116, pp. 348\u2013359. Springer, Berlin (2006)."},{"key":"9864_CR15","unstructured":"Gama N., Nguyen P.Q., Regev O.: Lattice enumeration using extreme pruning. In: Gilbert H. (ed.) Advances in Cryptology\u2014EUROCRYPT 2010. Lecture Notes in Computer Science, vol. 6110, pp. 257\u2013278. Springer, Berlin (2010)."},{"key":"9864_CR16","doi-asserted-by":"crossref","unstructured":"Gentry C.: A fully homomorphic encryption scheme. Ph.D. thesis, Stanford University. http:\/\/crypto.stanford.edu\/craig (2009).","DOI":"10.1145\/1536414.1536440"},{"key":"9864_CR17","doi-asserted-by":"crossref","unstructured":"Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC 08: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 197\u2013206. ACM (2008).","DOI":"10.1145\/1374376.1374407"},{"key":"9864_CR18","unstructured":"Hanrot G., Pujol X., Stehl\u00e9, D.: Algorithms for the shortest and closest lattice vector problems. In: Chee Y.M., Guo Z., Ling S., Shao F., Tang Y., Wang H., Xing C. (eds.) IWCC. Lecture Notes in Computer Science, vol. 6639, pp. 159\u2013190. Springer, Berlin (2011)."},{"key":"9864_CR19","unstructured":"Hanrot G., Pujol X., Stehl\u00e9 D.: Analyzing blockwise lattice algorithms using dynamical systems. In: Rogaway P. (ed.) Advances in Cryptology\u2014CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 447\u2013464. Springer, Berlin (2011)."},{"key":"9864_CR20","unstructured":"Johansson F. et al.: mpmath: a Python library for arbitrary-precision floating-point arithmetic (version 0.17), February 2011. http:\/\/code.google.com\/p\/mpmath\/ . Accessed 30 June 2013."},{"key":"9864_CR21","unstructured":"Lindner R., Peikert C.: Better key sizes (and attacks) for LWE-based encryption. In: Topics in Cryptology\u2014CT-RSA 2011. Lecture Notes in Computer Science, vol. 6558, pp. 319\u2013339, Springer, Berlin (2011)."},{"key":"9864_CR22","unstructured":"Liu M., Nguyen P.Q.: Solving BDD by enumeration: An update. In: Dawson E. (ed.) CT-RSA. Lecture Notes in Computer Science, vol. 7779, pp. 293\u2013309. Springer, Berlin (2013)."},{"key":"9864_CR23","unstructured":"Lyubashevsky V., Micciancio D., Peikert C., Rosen A.: SWIFFT: A modest proposal for FFT hashing. In: Nyberg K. (ed.) Fast Software Encryption. Lecture Notes in Computer Science, vol. 5086, pp. 54\u201372. Springer, Berlin (2008)."},{"key":"9864_CR24","unstructured":"Micciancio D., Regev O.: Lattice-based cryptography. In: Bernstein D.J., Buchmann J., Dahmen E. (eds.) Post-Quantum Cryptography, pp. 147\u2013191. Springer, Berlin (2009)."},{"key":"9864_CR25","unstructured":"Morel I., Stehl\u00e9 D., Villard G.: H-LLL: using householder inside LLL. In: Johnson J.R., Park H., Kaltofen E. (eds) Symbolic and Algebraic Computation, International Symposium, ISSAC, 2009 pp. 271\u2013278. ACM (2009)."},{"key":"9864_CR26","unstructured":"Nguyen P.Q.: Lattice reduction algorithms: theory and practice. In: Paterson K.G. (eds.) Advances in Cryptology\u2014EUROCRYPT 2011. Lecture Notes in Computer Science, vol. 6632, pp. 2\u20136. Springer, Berlin (2011)."},{"key":"9864_CR27","doi-asserted-by":"crossref","unstructured":"Nguyen P.Q., Stehl\u00e9 D.: Low-dimensional lattice basis reduction revisited. ACM Trans. Algorithms 5(4) (2009).","DOI":"10.1145\/1597036.1597050"},{"key":"9864_CR28","unstructured":"Pujol X., Stehl\u00e9 D.: Solving the shortest lattice vector problem in time $$2^{2.465n}$$ 2 2.465 n . IACR Cryptology ePrint Archive 2009:605 (2009)."},{"key":"9864_CR29","doi-asserted-by":"crossref","unstructured":"Regev O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM. 56(6), 84\u201393 (2009).","DOI":"10.1145\/1568318.1568324"},{"key":"9864_CR30","doi-asserted-by":"crossref","unstructured":"Regev O.: The learning with errors problem (invited survey). In: IEEE Conference on Computational Complexity, pp. 191\u2013204. IEEE Computer Society (2010).","DOI":"10.1109\/CCC.2010.26"},{"key":"9864_CR31","unstructured":"R\u00fcckert M., Schneider M.: Estimating the security of lattice-based cryptosystems. IACR Cryptology ePrint Archive 2010, 137 (2010)."},{"key":"9864_CR32","unstructured":"Stein W.A. et al.: Sage Mathematics Software (Version 5.2). The Sage Development Team, http:\/\/www.sagemath.org (2012). Accessed 30 June 2013."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-013-9864-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10623-013-9864-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-013-9864-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,18]],"date-time":"2019-07-18T15:00:58Z","timestamp":1563462058000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10623-013-9864-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,19]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["9864"],"URL":"https:\/\/doi.org\/10.1007\/s10623-013-9864-x","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,19]]}}}