{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T14:57:21Z","timestamp":1773154641932,"version":"3.50.1"},"publisher-location":"Cham","reference-count":73,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030842444","type":"print"},{"value":"9783030842451","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-84245-1_26","type":"book-chapter","created":{"date-parts":[[2021,8,10]],"date-time":"2021-08-10T23:04:26Z","timestamp":1628636666000},"page":"760-790","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Towards Faster Polynomial-Time Lattice Reduction"],"prefix":"10.1007","author":[{"given":"Paul","family":"Kirchner","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Espitau","sequence":"additional","affiliation":[]},{"given":"Pierre-Alain","family":"Fouque","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,11]]},"reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/978-3-030-56880-1_10","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"D Aggarwal","year":"2020","unstructured":"Aggarwal, D., Li, J., Nguyen, P.Q., Stephens-Davidowitz, N.: Slide reduction, revisited\u2014filling the gaps in SVP approximation. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 274\u2013295. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56880-1_10"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: SODA , pp. 10\u201324 (2016)","DOI":"10.1137\/1.9781611974331.ch2"},{"key":"26_CR3","unstructured":"Albrecht, M., Bai, S., Cad\u00e9, D., Pujol, X., Stehl\u00e9, D.: fpLLL-5.0, a floating-point LLL implementation (2017). http:\/\/perso.ens-lyon.fr\/damien.stehle"},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-662-53018-4_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"M Albrecht","year":"2016","unstructured":"Albrecht, M., Bai, S., Ducas, L.: A subfield lattice attack on overstretched NTRU assumptions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 153\u2013178. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53018-4_6"},{"key":"26_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/978-3-030-56880-1_7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"MR Albrecht","year":"2020","unstructured":"Albrecht, M.R., Bai, S., Fouque, P.-A., Kirchner, P., Stehl\u00e9, D., Wen, W.: Faster enumeration-based lattice reduction: root Hermite factor $$k^{1\/(2k)}$$ time $$k^{k\/8+o(k)}$$. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 186\u2013212. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56880-1_7"},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/978-3-030-17656-3_25","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"MR Albrecht","year":"2019","unstructured":"Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., Stevens, M.: The general sieve kernel and new records in lattice reduction. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part II. LNCS, vol. 11477, pp. 717\u2013746. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17656-3_25"},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-030-03326-2_13","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2018","author":"S Bai","year":"2018","unstructured":"Bai, S., Stehl\u00e9, D., Wen, W.: Measuring, simulating and exploiting the head concavity phenomenon in BKZ. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part I. LNCS, vol. 11272, pp. 369\u2013404. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-03326-2_13"},{"issue":"236","key":"26_CR8","doi-asserted-by":"publisher","first-page":"1719","DOI":"10.1090\/S0025-5718-00-01278-3","volume":"70","author":"D Bailey","year":"2001","unstructured":"Bailey, D., Broadhurst, D.: Parallel integer relation detection: techniques and applications. Math. Comput. 70(236), 1719\u20131736 (2001)","journal-title":"Math. Comput."},{"issue":"5","key":"26_CR9","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1016\/j.jsc.2003.09.003","volume":"37","author":"K Belabas","year":"2004","unstructured":"Belabas, K.: A relative van Hoeij algorithm over number fields. J. Symb. Comput. 37(5), 641\u2013668 (2004)","journal-title":"J. Symb. Comput."},{"issue":"1","key":"26_CR10","doi-asserted-by":"publisher","first-page":"15","DOI":"10.5802\/jtnb.655","volume":"21","author":"K Belabas","year":"2009","unstructured":"Belabas, K., van Hoeij, M., Kl\u00fcners, J., Steel, A.: Factoring polynomials over global fields. Journal de th\u00e9orie des nombres de Bordeaux 21(1), 15\u201339 (2009)","journal-title":"Journal de th\u00e9orie des nombres de Bordeaux"},{"key":"26_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-642-54631-0_11","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"J Bi","year":"2014","unstructured":"Bi, J., Coron, J.-S., Faug\u00e8re, J.-C., Nguyen, P.Q., Renault, G., Zeitoun, R.: Rounding and chaining LLL: finding faster small roots of univariate polynomial congruences. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 185\u2013202. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54631-0_11"},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-642-45239-0_4","volume-title":"Cryptography and Coding","author":"JW Bos","year":"2013","unstructured":"Bos, J.W., Lauter, K., Loftus, J., Naehrig, M.: Improved security for a ring-based fully homomorphic encryption scheme. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 45\u201364. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-45239-0_4"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/3-540-58691-1_54","volume-title":"Algorithmic Number Theory","author":"J Buchmann","year":"1994","unstructured":"Buchmann, J.: Reducing lattice bases by means of approximations. In: Adleman, L.M., Huang, M.-D. (eds.) ANTS 1994. LNCS, vol. 877, pp. 160\u2013168. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-58691-1_54"},{"key":"26_CR14","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). https:\/\/doi.org\/10.1007\/978-3-642-25385-0_1"},{"key":"26_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-38348-9_20","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"JH Cheon","year":"2013","unstructured":"Cheon, J.H., et al.: Batch fully homomorphic encryption over the integers. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 315\u2013335. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38348-9_20"},{"key":"26_CR16","unstructured":"Cheon, J.H., Hhan, M., Lee, C.: Cryptanalysis of middle lattice on the overstretched NTRU problem for general modulus polynomial. Cryptology ePrint Archive, Report 2017\/484 (2017). http:\/\/eprint.iacr.org\/2017\/484"},{"key":"26_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/978-3-662-46800-5_20","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2015","author":"JH Cheon","year":"2015","unstructured":"Cheon, J.H., Stehl\u00e9, D.: Fully homomophic encryption over the integers revisited. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 513\u2013536. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46800-5_20"},{"key":"26_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A Course in Computational Algebraic Number Theory","author":"H Cohen","year":"1993","unstructured":"Cohen, H.: A Course in Computational Algebraic Number Theory. Springer, New York (1993). https:\/\/doi.org\/10.1007\/978-3-662-02945-9"},{"issue":"4","key":"26_CR19","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s001459900030","volume":"10","author":"D Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233\u2013260 (1997)","journal-title":"J. Cryptol."},{"key":"26_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-69053-0_5","volume-title":"Advances in Cryptology \u2014 EUROCRYPT \u201997","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). https:\/\/doi.org\/10.1007\/3-540-69053-0_5"},{"key":"26_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/978-3-642-40041-4_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"J-S Coron","year":"2013","unstructured":"Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 476\u2013493. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_26"},{"key":"26_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-642-54631-0_18","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"J-S Coron","year":"2014","unstructured":"Coron, J.-S., Lepoint, T., Tibouchi, M.: Scale-invariant fully homomorphic encryption over the integers. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 311\u2013328. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54631-0_18"},{"key":"26_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-662-47989-6_13","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"J-S Coron","year":"2015","unstructured":"Coron, J.-S., Lepoint, T., Tibouchi, M.: New multilinear maps over the integers. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 267\u2013286. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47989-6_13"},{"key":"26_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-642-22792-9_28","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"J-S Coron","year":"2011","unstructured":"Coron, J.-S., Mandal, A., Naccache, D., Tibouchi, M.: Fully homomorphic encryption over the integers with shorter public keys. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 487\u2013504. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22792-9_28"},{"key":"26_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-642-29011-4_27","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"J-S Coron","year":"2012","unstructured":"Coron, J.-S., Naccache, D., Tibouchi, M.: Public key compression and modulus switching for fully homomorphic encryption over the integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 446\u2013464. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_27"},{"key":"26_CR26","unstructured":"Ducas, L., Stevens, M., van Woerden, W.: Advanced lattice sieving on GPUs, with tensor cores. Cryptology ePrint Archive, Report 2021\/141 (2021). https:\/\/eprint.iacr.org\/2021\/141"},{"issue":"2","key":"26_CR27","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1236463.1236468","volume":"33","author":"L Fousse","year":"2007","unstructured":"Fousse, L., Hanrot, G., Lef\u00e8vre, V., P\u00e9lissier, P., Zimmermann, P.: MPFR: a multiple-precision binary floating-point library with correct rounding. ACM Trans. Math. Softw. (TOMS) 33(2), 13 (2007)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"key":"26_CR28","unstructured":"Frieze, A.M., Kannan, R., Lagarias, J.C.:. Linear congruential generators do not produce random sequences. In: 25th FOCS, pp. 480\u2013484. IEEE Computer Society Press (1984)"},{"key":"26_CR29","doi-asserted-by":"crossref","unstructured":"Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell\u2019s inequality. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 207\u2013216 (2008)","DOI":"10.1145\/1374376.1374408"},{"key":"26_CR30","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). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_13"},{"key":"26_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/978-3-030-34621-8_17","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2019","author":"N Genise","year":"2019","unstructured":"Genise, N., Gentry, C., Halevi, S., Li, B., Micciancio, D.: Homomorphic encryption for finite automata. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part II. LNCS, vol. 11922, pp. 473\u2013502. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-34621-8_17"},{"key":"26_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/3-540-44987-6_12","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2001","author":"C Gentry","year":"2001","unstructured":"Gentry, C.: Key recovery and message attacks on NTRU-composite. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 182\u2013194. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44987-6_12"},{"key":"26_CR33","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169\u2013178. ACM Press (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"26_CR34","volume-title":"Matrix Computations","author":"GH Golub","year":"1996","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996)","edition":"3"},{"key":"26_CR35","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). https:\/\/doi.org\/10.1007\/978-3-642-22792-9_25"},{"key":"26_CR36","unstructured":"Hanrot, G., Pujol, X., Stehl\u00e9, D.: Terminating BKZ. Cryptology ePrint Archive, Report 2011\/198 (2011). http:\/\/eprint.iacr.org\/2011\/198"},{"issue":"5","key":"26_CR37","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/0218059","volume":"18","author":"J H\u00e5stad","year":"1989","unstructured":"H\u00e5stad, J., Just, B., Lagarias, J.C., Schnorr, C.: Polynomial time algorithms for finding integer relations among real numbers. SIAM J. Comput. 18(5), 859\u2013881 (1989)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"26_CR38","doi-asserted-by":"publisher","first-page":"1295","DOI":"10.1137\/S0097539795295626","volume":"27","author":"C Heckler","year":"1998","unstructured":"Heckler, C., Thiele, L.: Complexity analysis of a parallel lattice basis reduction algorithm. SIAM J. Comput. 27(5), 1295\u20131302 (1998)","journal-title":"SIAM J. Comput."},{"key":"26_CR39","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718027","volume-title":"Accuracy and Stability of Numerical Algorithms","author":"NJ Higham","year":"2002","unstructured":"Higham, N.J.: Accuracy and Stability of Numerical Algorithms, vol. 80. SIAM, Philadelphia (2002)"},{"issue":"3","key":"26_CR40","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s001459900042","volume":"11","author":"A Joux","year":"1998","unstructured":"Joux, A., Stern, J.: Lattice reduction: a toolbox for the cryptanalyst. J. Cryptol. 11(3), 161\u2013185 (1998). https:\/\/doi.org\/10.1007\/s001459900042","journal-title":"J. Cryptol."},{"key":"26_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-030-56880-1_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"P Kirchner","year":"2020","unstructured":"Kirchner, P., Espitau, T., Fouque, P.-A.: Fast reduction of algebraic lattices over cyclotomic fields. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 155\u2013185. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56880-1_6"},{"key":"26_CR42","unstructured":"Kirchner, P., Espitau, T., Fouque, P.-A.: Algebraic and Euclidean lattices: optimal lattice reduction and beyond. Cryptology ePrint Archive, Report 2019\/1436 (2019). https:\/\/eprint.iacr.org\/2019\/1436"},{"key":"26_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-56620-7_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"P Kirchner","year":"2017","unstructured":"Kirchner, P., Fouque, P.-A.: Revisiting lattice attacks on overstretched NTRU parameters. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I. LNCS, vol. 10210, pp. 3\u201326. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56620-7_1"},{"key":"26_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-44670-2_7","volume-title":"Cryptography and Lattices","author":"H Koy","year":"2001","unstructured":"Koy, H., Schnorr, C.P.: Segment LLL-reduction of lattice bases. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 67\u201380. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44670-2_7"},{"key":"26_CR45","doi-asserted-by":"crossref","unstructured":"Lagarias, J.C.: The computational complexity of simultaneous diophantine approximation problems. In: 23rd FOCS, pp. 32\u201339. IEEE Computer Society Press (1982)","DOI":"10.1109\/SFCS.1982.43"},{"key":"26_CR46","doi-asserted-by":"publisher","unstructured":"Lagarias, J.C.: Knapsack public key cryptosystems and diophantine approximation. In: Chaum, D. (ed.) CRYPTO\u201983, pp. 3\u201323. Springer, Boston (1984). https:\/\/doi.org\/10.1007\/978-1-4684-4730-9_1","DOI":"10.1007\/978-1-4684-4730-9_1"},{"issue":"4","key":"26_CR47","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF02128669","volume":"10","author":"JC Lagarias","year":"1990","unstructured":"Lagarias, J.C., Lenstra, H.W., Schnorr, C.: Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica 10(4), 333\u2013348 (1990). https:\/\/doi.org\/10.1007\/BF02128669","journal-title":"Combinatorica"},{"key":"26_CR48","doi-asserted-by":"crossref","unstructured":"Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. In: 24th FOCS, pp. 1\u201310. IEEE Computer Society Press, November 1983","DOI":"10.1109\/SFCS.1983.70"},{"key":"26_CR49","unstructured":"Lee, C., Wallet, A.: Lattice analysis on MiNTRU problem. Cryptology ePrint Archive, Report 2020\/230 (2020). https:\/\/eprint.iacr.org\/2020\/230"},{"key":"26_CR50","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W.J., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"26_CR51","doi-asserted-by":"crossref","unstructured":"Maze, G.: Some inequalities related to the Seysen measure of a lattice (2010)","DOI":"10.1016\/j.laa.2010.06.017"},{"key":"26_CR52","doi-asserted-by":"publisher","unstructured":"Mehlhorn, K., Sanders, P.: Algorithms and Data Structures: The Basic Toolbox. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-77978-0","DOI":"10.1007\/978-3-540-77978-0"},{"key":"26_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1007\/978-3-662-49890-3_31","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"D Micciancio","year":"2016","unstructured":"Micciancio, D., Walter, M.: Practical, predictable lattice basis reduction. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 820\u2013849. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49890-3_31"},{"issue":"261","key":"26_CR54","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1090\/S0025-5718-07-02017-0","volume":"77","author":"N M\u00f6ller","year":"2008","unstructured":"M\u00f6ller, N.: On Sch\u00f6nhage\u2019s algorithm and subquadratic integer GCD computation. Math. Comput. 77(261), 589\u2013607 (2008)","journal-title":"Math. Comput."},{"key":"26_CR55","doi-asserted-by":"crossref","unstructured":"Neumaier, A., Stehl\u00e9, D.: Faster LLL-type reduction of lattice bases. In: ISSAC, pp. 373\u2013380 (2016)","DOI":"10.1145\/2930889.2930917"},{"key":"26_CR56","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 Nguyen","year":"2006","unstructured":"Nguyen, 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). https:\/\/doi.org\/10.1007\/11792086_18"},{"issue":"3","key":"26_CR57","doi-asserted-by":"publisher","first-page":"874","DOI":"10.1137\/070705702","volume":"39","author":"PQ Nguyen","year":"2009","unstructured":"Nguyen, P.Q., Stehl\u00e9, D.: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39(3), 874\u2013903 (2009)","journal-title":"SIAM J. Comput."},{"key":"26_CR58","doi-asserted-by":"crossref","unstructured":"Novocin, A., Stehl\u00e9, D., Villard, G.: An LLL-reduction algorithm with quasi-linear time complexity. In: 43rd STOC, pp. 403\u2013412. ACM (2011)","DOI":"10.1145\/1993636.1993691"},{"key":"26_CR59","unstructured":"Pataki, G., Tural, M.: Lattice determinants in reduced bases. arXiv:0804.4014 (2008)"},{"key":"26_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1007\/978-3-030-17656-3_24","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"A Pellet-Mary","year":"2019","unstructured":"Pellet-Mary, A., Hanrot, G., Stehl\u00e9, D.: Approx-SVP in ideal lattices with pre-processing. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part II. LNCS, vol. 11477, pp. 685\u2013716. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17656-3_24"},{"key":"26_CR61","unstructured":"Morel, I., Stehl\u00e9, D., Villard, G.: LLL reducing with the most significant bits. In: Nabeshima, K., Nagasaka, K., Winkler, F., Sz\u00e1nt\u00f3, \u00c1. (eds.) ISSAC, pp. 367\u2013374. ACM (2014)"},{"key":"26_CR62","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"C Schnorr","year":"1987","unstructured":"Schnorr, C.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53, 201\u2013224 (1987)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"26_CR63","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0196-6774(88)90004-1","volume":"9","author":"C Schnorr","year":"1988","unstructured":"Schnorr, C.: A more efficient algorithm for lattice basis reduction. J. Algorithms 9(1), 47\u201362 (1988)","journal-title":"J. Algorithms"},{"key":"26_CR64","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1017\/S0963548300001371","volume":"3","author":"C Schnorr","year":"1994","unstructured":"Schnorr, C.: Block reduced lattice bases and successive minima. Comb. Probab. Comput. 3, 507\u2013522 (1994)","journal-title":"Comb. Probab. Comput."},{"key":"26_CR65","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/3-540-13345-3_40","volume-title":"Automata, Languages and Programming","author":"A Sch\u00f6nhage","year":"1984","unstructured":"Sch\u00f6nhage, A.: Factorization of univariate integer polynomials by diophantine approximation and an improved basis reduction algorithm. In: Paredaens, J. (ed.) ICALP 1984. LNCS, vol. 172, pp. 436\u2013447. Springer, Heidelberg (1984). https:\/\/doi.org\/10.1007\/3-540-13345-3_40"},{"key":"26_CR66","doi-asserted-by":"crossref","unstructured":"Sch\u00f6nhage, A.: Fast reduction and composition of binary quadratic forms. In: ISSAC, pp. 128\u2013133. ACM (1991)","DOI":"10.1145\/120694.120711"},{"issue":"3","key":"26_CR67","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/BF01202355","volume":"13","author":"M Seysen","year":"1993","unstructured":"Seysen, M.: Simultaneous reduction of a lattice basis and its reciprocal basis. Combinatorica 13(3), 363\u2013376 (1993)","journal-title":"Combinatorica"},{"key":"26_CR68","doi-asserted-by":"publisher","unstructured":"Stehl\u00e9, D.: Floating-point LLL: theoretical and practical aspects. In: Nguyen, P., Vall\u00e9e, B. (eds.) The LLL Algorithm, pp. 179\u2013213. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02295-1_5","DOI":"10.1007\/978-3-642-02295-1_5"},{"key":"26_CR69","doi-asserted-by":"crossref","unstructured":"Stern, J.: Secret linear congruential generators are not cryptographically secure. In: 28th FOCS, pp. 421\u2013426. IEEE Computer Society Press, October 1987","DOI":"10.1109\/SFCS.1987.51"},{"key":"26_CR70","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-13190-5_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"M van Dijk","year":"2010","unstructured":"van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24\u201343. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_2"},{"issue":"2","key":"26_CR71","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0022-314X(01)92763-5","volume":"95","author":"M Van Hoeij","year":"2002","unstructured":"Van Hoeij, M.: Factoring polynomials and the knapsack problem. J. Number Theor. 95(2), 167\u2013189 (2002)","journal-title":"J. Number Theor."},{"key":"26_CR72","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/978-3-642-12200-2_47","volume-title":"LATIN 2010: Theoretical Informatics","author":"M van Hoeij","year":"2010","unstructured":"van Hoeij, M., Novocin, A.: Gradual sub-lattice reduction and a new complexity for factoring polynomials. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 539\u2013553. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12200-2_47"},{"key":"26_CR73","doi-asserted-by":"crossref","unstructured":"Villard, G.: Parallel lattice basis reduction. In: ISSAC, pp. 269\u2013277 (1992)","DOI":"10.1145\/143242.143327"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2021"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-84245-1_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,11]],"date-time":"2024-08-11T00:03:17Z","timestamp":1723334597000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-84245-1_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030842444","9783030842451"],"references-count":73,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-84245-1_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"11 August 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 August 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 August 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"41","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"426","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"103","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20.9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1 invited paper is also included.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}