{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T14:56:58Z","timestamp":1773154618571,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":51,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662498897","type":"print"},{"value":"9783662498903","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49890-3_30","type":"book-chapter","created":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T04:40:46Z","timestamp":1461732046000},"page":"789-819","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":85,"title":["Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator"],"prefix":"10.1007","author":[{"given":"Yoshinori","family":"Aono","sequence":"first","affiliation":[]},{"given":"Yuntao","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Takuya","family":"Hayashi","sequence":"additional","affiliation":[]},{"given":"Tsuyoshi","family":"Takagi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,28]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in $$2^n$$ time using discrete Gaussian sampling: extended abstract. In: STOC 2015, pp. 733\u2013742 (2015)","DOI":"10.1109\/FOCS.2015.41"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: The shortest vector problem in $$L_2$$ is NP-hard for randomized reductions. In: STOC, pp. 10\u201319 (1998)","DOI":"10.1145\/276698.276705"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: The worst-case behavior of Schnorr\u2019s algorithm approximating the shortest nonzero vector in a lattice. In: STOC, pp. 396\u2013406 (2003)","DOI":"10.1145\/780542.780602"},{"key":"30_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/978-3-319-12160-4_18","volume-title":"Information Security and Cryptology \u2013 ICISC 2013","author":"MR Albrecht","year":"2014","unstructured":"Albrecht, M.R., Fitzpatrick, R., G\u00f6pfert, F.: On the efficacy of solving LWE by reduction to Unique-SVP. In: Lee, H.-S., Han, D.-G. (eds.) ICISC 2013. LNCS, vol. 8565, pp. 293\u2013310. Springer, Heidelberg (2014)"},{"issue":"3","key":"30_CR5","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1515\/jmc-2015-0016","volume":"9","author":"MR Albrecht","year":"2015","unstructured":"Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptology 9(3), 169\u2013203 (2015)","journal-title":"J. Math. Cryptology"},{"key":"30_CR6","unstructured":"Aono, Y.: A faster method for computing Gama-Nguyen-Regev\u2019s extreme pruning coefficients (2014). arXiv:1406.0342"},{"key":"30_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-03515-4_1","volume-title":"Progress in Cryptology \u2013 INDOCRYPT 2013","author":"Y Aono","year":"2013","unstructured":"Aono, Y., Boyen, X., Phong, L.T., Wang, L.: Key-private proxy re-encryption under LWE. In: Paul, G., Vaudenay, S. (eds.) INDOCRYPT 2013. LNCS, vol. 8250, pp. 1\u201318. Springer, Heidelberg (2013)"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"Aono, Y., Wang, Y., Hayashi, T., Takagi, T.: Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. In: IACR Cryptology ePrint Archive 2016: 146 (2016)","DOI":"10.1007\/978-3-662-49890-3_30"},{"key":"30_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/978-3-319-08344-5_21","volume-title":"Information Security and Privacy","author":"S Bai","year":"2014","unstructured":"Bai, S., Galbraith, S.D.: Lattice decoding attacks on binary LWE. In: Susilo, W., Mu, Y. (eds.) ACISP 2014. LNCS, vol. 8544, pp. 322\u2013337. Springer, Heidelberg (2014)"},{"key":"30_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-642-22792-9_29","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"Z Brakerski","year":"2011","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from Ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 505\u2013524. Springer, Heidelberg (2011)"},{"key":"30_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/11792086_17","volume-title":"Algorithmic Number Theory","author":"J Buchmann","year":"2006","unstructured":"Buchmann, J., Ludwig, C.: Practical lattice basis sampling reduction. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 222\u2013237. Springer, Heidelberg (2006)"},{"key":"30_CR12","unstructured":"Chen, Y.: R\u00e9duction de r\u00e9seau et s\u00e9curit\u00e9 concr\u00e8te du chiffrement compl\u00e8tement homomorphe, Doctoral dissertation (2013)"},{"key":"30_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-25385-0_1","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"Y Chen","year":"2011","unstructured":"Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1\u201320. Springer, Heidelberg (2011)"},{"key":"30_CR14","unstructured":"Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates, the full version. http:\/\/www.di.ens.fr\/~ychen\/research\/Full_BKZ.pdf"},{"key":"30_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/3-540-69053-0_5","volume-title":"Advances in Cryptology - EUROCRYPT 1997","author":"D Coppersmith","year":"1997","unstructured":"Coppersmith, D., Shamir, A.: Lattice attacks on NTRU. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 52\u201361. Springer, Heidelberg (1997)"},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1090\/S0025-5718-1985-0777278-8","volume":"44","author":"U Fincke","year":"1985","unstructured":"Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comp. 44, 463\u2013471 (1985)","journal-title":"Math. Comp."},{"key":"30_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/3-540-46665-7_29","volume-title":"Cryptography and Coding","author":"R Fischlin","year":"1999","unstructured":"Fischlin, R., Seifert, J.-P.: Tensor-based trapdoors for CVP and their application to public key cryptography. In: Walker, M. (ed.) Cryptography and Coding 1999. LNCS, vol. 1746, pp. 244\u2013257. Springer, Heidelberg (1999)"},{"issue":"1","key":"30_CR18","first-page":"67","volume":"23","author":"M Fukase","year":"2015","unstructured":"Fukase, M., Kashiwabara, K.: An accelerated algorithm for solving SVP based on statistical analysis. J. Inf. Process. 23(1), 67\u201380 (2015)","journal-title":"J. Inf. Process."},{"key":"30_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-78967-3_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"N Gama","year":"2008","unstructured":"Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31\u201351. Springer, Heidelberg (2008)"},{"key":"30_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-642-13190-5_13","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"N Gama","year":"2010","unstructured":"Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257\u2013278. Springer, Heidelberg (2010)"},{"key":"30_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-38348-9_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"S Garg","year":"2013","unstructured":"Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1\u201317. Springer, Heidelberg (2013)"},{"key":"30_CR22","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169\u2013178 (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"30_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-642-22792-9_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"G Hanrot","year":"2011","unstructured":"Hanrot, G., Pujol, X., Stehl\u00e9, D.: Analyzing blockwise lattice algorithms using dynamical systems. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 447\u2013464. Springer, Heidelberg (2011)"},{"key":"30_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-540-74143-5_10","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"G Hanrot","year":"2007","unstructured":"Hanrot, G., Stehl\u00e9, D.: Improved Analysis of Kannan\u2019s shortest lattice vector algorithm. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 170\u2013186. Springer, Heidelberg (2007)"},{"key":"30_CR25","unstructured":"Haque, M., Rahman, M.O., Pieprzyk, J.: Analysing progressive-BKZ lattice reduction algorithm. In: NCICIT 2013, pp. 73\u201380 (2013)"},{"key":"30_CR26","volume-title":"An Introduction to Mathematical Cryptography","author":"J Hoffstein","year":"2008","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H.: An Introduction to Mathematical Cryptography. Springer-Verlag New York, New York (2008)"},{"key":"30_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-642-54631-0_24","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"T Ishiguro","year":"2014","unstructured":"Ishiguro, T., Kiyomoto, S., Miyake, Y., Takagi, T.: Parallel Gauss Sieve algorithm: solving the SVP challenge over a 128-dimensional ideal lattice. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 411\u2013428. Springer, Heidelberg (2014)"},{"key":"30_CR28","doi-asserted-by":"crossref","unstructured":"Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: STOC, pp. 193\u2013206 (1983)","DOI":"10.1145\/800061.808749"},{"issue":"3","key":"30_CR29","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/BF01442795","volume":"6","author":"A Korkine","year":"1873","unstructured":"Korkine, A., Zolotareff, G.: Sur les formes quadratiques. Math. Ann. 6(3), 366\u2013389 (1873)","journal-title":"Math. Ann."},{"issue":"4","key":"30_CR30","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra Jr., H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"30_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-319-06734-6_20","volume-title":"Progress in Cryptology \u2013 AFRICACRYPT 2014","author":"T Lepoint","year":"2014","unstructured":"Lepoint, T., Naehrig, M.: A comparison of the homomorphic encryption schemes FV and YASHE. In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT 2014. LNCS, vol. 8469, pp. 318\u2013335. Springer, Heidelberg (2014)"},{"key":"30_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-19074-2_21","volume-title":"Topics in Cryptology \u2013 CT-RSA 2011","author":"R Lindner","year":"2011","unstructured":"Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319\u2013339. Springer, Heidelberg (2011)"},{"key":"30_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/978-3-642-36095-4_19","volume-title":"Topics in Cryptology \u2013 CT-RSA 2013","author":"M Liu","year":"2013","unstructured":"Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: an update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 293\u2013309. Springer, Heidelberg (2013)"},{"key":"30_CR34","doi-asserted-by":"crossref","unstructured":"Micciancio, D.: The shortest vector problem is NP-hard to approximate to within some constant. In: FOCS, pp. 92\u201398 (1998)","DOI":"10.1109\/SFCS.1998.743432"},{"key":"30_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/3-540-48405-1_18","volume-title":"Advances in Cryptology - CRYPTO 1999","author":"PQ Nguy\u00ean","year":"1999","unstructured":"Nguy\u00ean, P.Q.: Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto\u201997. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 288\u2013304. Springer, Heidelberg (1999)"},{"key":"30_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/11761679_17","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"PQ Nguy\u00ean","year":"2006","unstructured":"Nguy\u00ean, P.Q., Regev, O.: Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 271\u2013288. Springer, Heidelberg (2006)"},{"key":"30_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11792086_18","volume-title":"Algorithmic Number Theory","author":"PQ Nguy\u00ean","year":"2006","unstructured":"Nguy\u00ean, P.Q., Stehl\u00e9, D.: LLL on the average. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 238\u2013256. Springer, Heidelberg (2006)"},{"key":"30_CR38","volume-title":"The LLL Algorithm: Survey and Applications","author":"PQ Nguyen","year":"2009","unstructured":"Nguyen, P.Q., Vall\u00e9e, B.: The LLL Algorithm: Survey and Applications. Springer-Verlag, Heidelberg (2009)"},{"key":"30_CR39","unstructured":"Plantard, T., Schneider, M.: Creating a challenge for ideal lattices. In: IACR Cryptology ePrint Archive 2013: 039 (2013)"},{"key":"30_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-642-39059-3_8","volume-title":"Information Security and Privacy","author":"T Plantard","year":"2013","unstructured":"Plantard, T., Susilo, W., Zhang, Z.: Adaptive precision floating point LLL. In: Boyd, C., Simpson, L. (eds.) ACISP 2013. LNCS, vol. 7959, pp. 104\u2013117. Springer, Heidelberg (2013)"},{"issue":"6","key":"30_CR41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"Oded Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), Article no. 34 (2009)","journal-title":"Journal of the ACM"},{"issue":"6","key":"30_CR42","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1112\/plms\/s3-6.2.305","volume":"3","author":"CA Rogers","year":"1956","unstructured":"Rogers, C.A.: The number of lattice points in a set. Proc. London Math. Soc. 3(6), 305\u2013320 (1956)","journal-title":"Proc. London Math. Soc."},{"issue":"2\u20133","key":"30_CR43","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"CP Schnorr","year":"1987","unstructured":"Schnorr, C.P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53(2\u20133), 201\u2013224 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/3-540-36494-3_14","volume-title":"STACS","author":"CP Schnorr","year":"2003","unstructured":"Schnorr, C.P.: Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 145\u2013156. Springer, Heidelberg (2003)"},{"key":"30_CR45","unstructured":"Schnorr, C.P.: Accelerated and Improved Slide- and LLL-Reduction. ECCC TR11-050 (2011)"},{"issue":"1\u20133","key":"30_CR46","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01581144","volume":"66","author":"CP Schnorr","year":"1994","unstructured":"Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(1\u20133), 181\u2013199 (1994)","journal-title":"Math. Program."},{"key":"30_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-49264-X_1","volume-title":"Advances in Cryptology - EUROCRYPT \u201995","author":"C-P Schnorr","year":"1995","unstructured":"Schnorr, C.-P., H\u00f6rner, H.H.: Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 1\u201312. Springer, Heidelberg (1995)"},{"key":"30_CR48","unstructured":"Schnorr, C.P., Shevchenko, T.: Solving subset sum problems of density close to 1 by \u201crandomized\u201d BKZ-reduction. In: IACR Cryptology ePrint Archive 2012: 620 (2012)"},{"key":"30_CR49","unstructured":"Shoup, V.: NTL: a library for ng number theory. http:\/\/www.shoup.net\/ntl\/"},{"key":"30_CR50","unstructured":"TU Darmstadt Lattice Challenge. http:\/\/www.latticechallenge.org\/"},{"key":"30_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-642-45239-0_17","volume-title":"Cryptography and Coding","author":"J van de Pol","year":"2013","unstructured":"van de Pol, J., Smart, N.P.: Estimating key sizes for high dimensional lattice-based systems. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 290\u2013303. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2016"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49890-3_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T22:03:33Z","timestamp":1748901813000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49890-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662498897","9783662498903"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49890-3_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"28 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}