{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T17:08:06Z","timestamp":1770743286536,"version":"3.49.0"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031866012","type":"print"},{"value":"9783031866029","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-86602-9_5","type":"book-chapter","created":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T00:02:53Z","timestamp":1742860973000},"page":"119-152","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Heuristic Algorithm for\u00a0Solving Restricted SVP and\u00a0Its Applications"],"prefix":"10.1007","author":[{"given":"Geng","family":"Wang","sequence":"first","affiliation":[]},{"given":"Wenwen","family":"Xia","sequence":"additional","affiliation":[]},{"given":"Dawu","family":"Gu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,15]]},"reference":[{"key":"5_CR1","unstructured":"Aggarwal, D., Mukhopadhyay, P.: Improved algorithms for the shortest vector problem and the closest vector problem in the infinity norm. In: Hsu, W.-L., Lee, D.-T., Liao, C.-S., editors, 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, volume 123 of LIPIcs, pp. 35:1\u201335:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case\/average-case equivalence. In: Leighton, F.T., Shor, P.W., editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pp. 284\u2013293. ACM (1997)","DOI":"10.1145\/258533.258604"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Bai, S., Fouque, P.-A., Kirchner, P., Stehl\u00e9, D., Wen, W.: Faster enumeration-based lattice reduction: root hermite factor $$\\text{k}^{\\text{1\/(2k) }}$$ time $$\\text{ k}^{\\text{ k\/8+o(k) }}$$. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part II, volume 12171 of Lecture Notes in Computer Science, pages 186\u2013212. Springer, 2020","DOI":"10.1007\/978-3-030-56880-1_7"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Bai, S., Li, J., Rowell, J.: Lattice reduction with approximate enumeration oracles - practical algorithms and concrete performance. In: Malkin, T., Peikert, C., editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part II, volume 12826 of Lecture Notes in Computer Science, pp. 732\u2013759. Springer (2021)","DOI":"10.1007\/978-3-030-84245-1_25"},{"key":"5_CR5","doi-asserted-by":"crossref","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., editors, Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part II, volume 11477 of Lecture Notes in Computer Science, pp. 717\u2013746. Springer (2019)","DOI":"10.1007\/978-3-030-17656-3_25"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Martin\u00a0R. Albrecht, Robert Fitzpatrick, and Florian G\u00f6pfert. On the efficacy of solving LWE by reduction to unique-SVP. In: Lee, H.-S., Han, D.-G., editors, Information Security and Cryptology - ICISC 2013 - 16th International Conference, Seoul, Korea, November 27-29, 2013, Revised Selected Papers, volume 8565 of Lecture Notes in Computer Science, pp. 293\u2013310. Springer (2013)","DOI":"10.1007\/978-3-319-12160-4_18"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Gheorghiu, V., Postlethwaite, E.W., Schanck, J.M.: Estimating quantum speedups for lattice sieves. In: Moriai, S., Wang, H., editors, Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part II, volume 12492 of Lecture Notes in Computer Science, pp. 583\u2013613. Springer (2020)","DOI":"10.1007\/978-3-030-64834-3_20"},{"key":"5_CR8","unstructured":"Alkim, E., Ducas, L., P\u00f6ppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: Holz, T., Savage, S., editors, 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016, pp. 327\u2013343. USENIX Association (2016)"},{"key":"5_CR9","unstructured":"Alwen, J., Krenn, S., Pietrzak, K., Wichs, D.: Learning with rounding, revisited - new reduction, properties and applications. In: Canetti, R., Garay, J.A., editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pp. 57\u201374. Springer (2013)"},{"key":"5_CR10","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: Fischlin, M., Coron, J.-S., editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, volume 9665 of Lecture Notes in Computer Science, pp. 789\u2013819. Springer (2016)","DOI":"10.1007\/978-3-662-49890-3_30"},{"key":"5_CR11","unstructured":"Avanzi, R., et al.: Crystals-kyber algorithm specifications and supporting documentation (version 3.0). NIST PQC Round 3 submissions (2020)"},{"issue":"1","key":"5_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L Babai","year":"1986","unstructured":"Babai, L.: On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1\u201313 (1986)","journal-title":"Combinatorica"},{"key":"5_CR13","unstructured":"Bai, S., et al.: Crystals-Dilithium algorithm specifications and supporting documentation. NIST PQC Round 3 submissions (2020)"},{"key":"5_CR14","unstructured":"Bai, S., Galbraith, S.D.: Lattice decoding attacks on binary LWE. In: Susilo, W., Mu, Y., editors, Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Wollongong, NSW, Australia, July 7-9, 2014. Proceedings, volume 8544 of Lecture Notes in Computer Science, pp. 322\u2013337. Springer (2014)"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"Bai, S., Stehl\u00e9, D., Wen, W.: Measuring, simulating and exploiting the head concavity phenomenon in BKZ. In: Peyrin, T., Galbraith, S.D., editors, Advances in Cryptology - ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part I, volume 11272 of Lecture Notes in Computer Science, pp. 369\u2013404. Springer (2018)","DOI":"10.1007\/978-3-030-03326-2_13"},{"key":"5_CR16","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: Krauthgamer, R., editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 10\u201324. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch2"},{"key":"5_CR17","unstructured":"Becker, A., Gama, N., Joux, A.: Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search. IACR Cryptol. ePrint Arch., 522 (2015)"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Bennett, H., Cheraghchi, M., Guruswami, V., Ribeiro, J.: Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all $$p$$ norms. In: Saha, B., Servedio, R.A., editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pp. 553\u2013566. ACM (2023)","DOI":"10.1145\/3564246.3585214"},{"key":"5_CR19","unstructured":"Chen, H.: A measure version of gaussian heuristic. IACR Cryptol. ePrint Arch., 439 (2016)"},{"key":"5_CR20","unstructured":"Chen, Y.: R\u00e9duction de r\u00e9seau et s\u00e9curit\u00e9 concr\u00e8te du chiffrement compl\u00e8tement homomorphe. PhD Thesis (2013)"},{"key":"5_CR21","unstructured":"Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X., editors, Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings, volume 7073 of Lecture Notes in Computer Science, pp. 1\u201320. Springer (2011)"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Dachman-Soled, D., Ducas, L., Gong, H., Rossi, M.: LWE with side information: attacks and concrete security estimation. In: Micciancio, D., Ristenpart, T., editors, Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part II, volume 12171 of Lecture Notes in Computer Science, pp. 329\u2013358. Springer (2020)","DOI":"10.1007\/978-3-030-56880-1_12"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Doulgerakis, E., Laarhoven, T., de\u00a0Weger, B.: Finding closest lattice vectors using approximate Voronoi cells. In: Ding, J., Steinwandt, R., editors, Post-Quantum Cryptography - 10th International Conference, PQCrypto 2019, Chongqing, China, May 8-10, 2019 Revised Selected Papers, volume 11505 of Lecture Notes in Computer Science, pp. 3\u201322. Springer (2019)","DOI":"10.1007\/978-3-030-25510-7_1"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Doulgerakis, E., Laarhoven, T., de\u00a0Weger, B.: Sieve, Enumerate, Slice, and Lift: - hybrid lattice algorithms for SVP via CVPP. In: Nitaj, A., Youssef, A.M., editors, Progress in Cryptology - AFRICACRYPT 2020 - 12th International Conference on Cryptology in Africa, Cairo, Egypt, July 20-22, 2020, Proceedings, volume 12174 of Lecture Notes in Computer Science, pp. 301\u2013320. Springer (2020)","DOI":"10.1007\/978-3-030-51938-4_15"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Ducas, L.: Shortest vector from lattice sieving: a few dimensions for free. In: Nielsen, J.B., Rijmen, V., editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I, volume 10820 of Lecture Notes in Computer Science, pp. 125\u2013145. Springer (2018)","DOI":"10.1007\/978-3-319-78381-9_5"},{"key":"5_CR26","doi-asserted-by":"crossref","unstructured":"Ducas, L., Laarhoven, T., van Woerden, W.P.J.: The randomized slicer for CVPP: sharper, faster, smaller, batchier. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V., editors, Public-Key Cryptography - PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4-7, 2020, Proceedings, Part II, volume 12111 of Lecture Notes in Computer Science, pp. 3\u201336. Springer (2020)","DOI":"10.1007\/978-3-030-45388-6_1"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Ducas, L., Stevens, M., van Woerden, W.P.J.: Advanced lattice sieving on GPUs, with tensor cores. In: Canteaut, a., Standaert, F.-X., editors, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part II, volume 12697 of Lecture Notes in Computer Science, pp. 249\u2013279. Springer (2021)","DOI":"10.1007\/978-3-030-77886-6_9"},{"issue":"1","key":"5_CR28","doi-asserted-by":"publisher","first-page":"251","DOI":"10.2140\/obs.2020.4.251","volume":"4","author":"T Espitau","year":"2020","unstructured":"Espitau, T., Kirchner, P.: The nearest-colattice algorithm: Time-approximation tradeoff for approx-CVP. Open Book Series 4(1), 251\u2013266 (2020)","journal-title":"Open Book Series"},{"issue":"3","key":"5_CR29","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"Kirshanova, E., Laarhoven, T.: Lower bounds on lattice sieving and information set decoding. In: Malkin, T., Peikert, C., editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part II, volume 12826 of Lecture Notes in Computer Science, pp. 791\u2013820. Springer (2021)","DOI":"10.1007\/978-3-030-84245-1_27"},{"issue":"3","key":"5_CR31","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10623-014-9938-4","volume":"75","author":"A Langlois","year":"2015","unstructured":"Langlois, A., Stehl\u00e9, D.: Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75(3), 565\u2013599 (2015)","journal-title":"Des. Codes Cryptogr."},{"issue":"4","key":"5_CR32","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., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"5_CR33","unstructured":"MATZOV. Report on the security of LWE: improved dual lattice attack. https:\/\/doi.org\/10.5281\/zenodo.6412487 (2022)"},{"key":"5_CR34","doi-asserted-by":"crossref","unstructured":"Mukhopadhyay, P.: Faster provable sieving algorithms for the shortest vector problem and the closest vector problem on lattices in P norm. Algorithms 14(12), 362 (2021)","DOI":"10.3390\/a14120362"},{"key":"5_CR35","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q.: Hermite\u2019s constant and lattice algorithms. In: Nguyen, P.Q., Vall\u00e9e, B., editors, The LLL Algorithm - Survey and Applications, Information Security and Cryptography, pp. 19\u201369. Springer (2010)","DOI":"10.1007\/978-3-642-02295-1_2"},{"issue":"2","key":"5_CR36","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1515\/JMC.2008.009","volume":"2","author":"PQ Nguyen","year":"2008","unstructured":"Nguyen, P.Q., Vidick, T.: Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptol. 2(2), 181\u2013207 (2008)","journal-title":"J. Math. Cryptol."},{"key":"5_CR37","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R., editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp. 84\u201393. ACM (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"5_CR38","doi-asserted-by":"crossref","unstructured":"Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. In: Budach, L., editor, Fundamentals of Computation Theory, 8th International Symposium, FCT \u201991, Gosen, Germany, September 9-13, 1991, Proceedings, volume 529 of Lecture Notes in Computer Science, pp. 68\u201385. Springer (1991)","DOI":"10.1007\/3-540-54458-5_51"},{"key":"5_CR39","unstructured":"Xia, W., Wang, L., Wang, G., Gu, D., Wang, B.: Improved progressive BKZ with lattice sieving. IACR Cryptol. ePrint Arch., 1343 (2022)"},{"key":"5_CR40","doi-asserted-by":"crossref","unstructured":"Xia, W., Wang, L., Wang, G., Gu, D., Wang, B.: A refined hardness estimation of LWE in two-step mode. In: Tang, Q., Teague, V., editors, Public-Key Cryptography - PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, Sydney, NSW, Australia, April 15-17, 2024, Proceedings, Part III, volume 14603 of Lecture Notes in Computer Science, pp. 3\u201335. Springer (2024)","DOI":"10.1007\/978-3-031-57725-3_1"}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-86602-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T00:03:18Z","timestamp":1742860998000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-86602-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031866012","9783031866029"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-86602-9_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"15 March 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PQCrypto","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Post-Quantum Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taipei","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 April 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pqcrypto2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/pqcrypto2025.iis.sinica.edu.tw\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}