{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T14:56:55Z","timestamp":1773154615709,"version":"3.50.1"},"reference-count":42,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T00:00:00Z","timestamp":1605571200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,11,17]]},"abstract":"Abstract<\/jats:title>\n \n We revisit the approximate Voronoi cells approach for solving the closest vector problem with preprocessing (CVPP) on high-dimensional lattices, and settle the open problem of Doulgerakis\u2013Laarhoven\u2013De Weger [PQCrypto, 2019] of determining exact asymptotics on the volume of these Voronoi cells under the Gaussian heuristic. As a result, we obtain improved upper bounds on the time complexity of the randomized iterative slicer when using less than\n \n \n \n \n \n 2<\/m:mn>\n \n 0.076<\/m:mn>\n d<\/m:mi>\n +<\/m:mo>\n o<\/m:mi>\n (<\/m:mo>\n d<\/m:mi>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:msup>\n <\/m:math>\n $2^{0.076d + o(d)}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n memory, and we show how to obtain time\u2013memory trade-offs even when using less than\n \n \n \n \n \n 2<\/m:mn>\n \n 0.048<\/m:mn>\n d<\/m:mi>\n +<\/m:mo>\n o<\/m:mi>\n (<\/m:mo>\n d<\/m:mi>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:msup>\n <\/m:math>\n $2^{0.048d + o(d)}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n memory. We also settle the open problem of obtaining a continuous trade-off between the size of the advice and the query time complexity, as the time complexity with subexponential advice in our approach scales as\n \n \n \n \n \n d<\/m:mi>\n \n d<\/m:mi>\n \n \/<\/m:mo>\n <\/m:mrow>\n 2<\/m:mn>\n +<\/m:mo>\n o<\/m:mi>\n (<\/m:mo>\n d<\/m:mi>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:msup>\n <\/m:math>\n $d^{d\/2 + o(d)}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n matching worst-case enumeration bounds, and achieving the same asymptotic scaling as average-case enumeration algorithms for the closest vector problem.\n <\/jats:p>","DOI":"10.1515\/jmc-2020-0074","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T15:54:48Z","timestamp":1606751688000},"page":"60-71","source":"Crossref","is-referenced-by-count":5,"title":["Approximate Voronoi cells for lattices, revisited"],"prefix":"10.1515","volume":"15","author":[{"given":"Thijs","family":"Laarhoven","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology , Eindhoven , The Netherlands"}]}],"member":"374","published-online":{"date-parts":[[2020,11,17]]},"reference":[{"key":"2025120600293909882_j_jmc-2020-0074_ref_001","doi-asserted-by":"crossref","unstructured":"Dorit Aharonov and Oded Regev, Lattice problems in NP \u2229 coNP, in: FOCS pp. 362\u2013371, 2004.","DOI":"10.1109\/FOCS.2004.35"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_002","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai and Cynthia Dwork, A public-key cryptosystem with worst-case\/average-case equivalence, in: STOC pp. 284\u2013293, 1997.","DOI":"10.1145\/258533.258604"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_003","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai, Ravi Kumar and Dandapani Sivakumar, A sieve algorithm for the shortest lattice vector problem, in: STOC pp. 601\u2013610, 2001.","DOI":"10.1145\/380752.380857"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_004","doi-asserted-by":"crossref","unstructured":"Martin R. Albrecht, L\u00e9o Ducas, Gottfried Herold, Elena Kirshanova, Eamonn Postlethwaite and Marc Stevens, The general sieve kernel and new records in lattice reduction, in: EUROCRYPT pp. 717\u2013746, 2019.","DOI":"10.1007\/978-3-030-17656-3_25"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_005","doi-asserted-by":"crossref","unstructured":"Yoshinori Aono and Phong Q. Nguy\u00ean, Random sampling revisited: lattice enumeration with discrete pruning, in: EURO-CRYPT pp. 65\u2013102, 2017.","DOI":"10.1007\/978-3-319-56614-6_3"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_006","doi-asserted-by":"crossref","unstructured":"Yoshinori Aono, Phong Q. Nguyen and Yixin Shen, Quantum lattice enumeration and tweaking discrete pruning, in: ASI-ACRYPT pp. 405\u2013434, 2018.","DOI":"10.1007\/978-3-030-03326-2_14"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_007","doi-asserted-by":"crossref","unstructured":"Anja Becker, L\u00e9o Ducas, Nicolas Gama and Thijs Laarhoven, New directions in nearest neighbor searching with applications to lattice sieving, in: SODA pp. 10\u201324, 2016.","DOI":"10.1137\/1.9781611974331.ch2"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_008","doi-asserted-by":"crossref","unstructured":"Daniel J. Bernstein, Johannes Buchmann and Erik Dahmen (eds.), Post-quantum cryptography Springer, 2009.","DOI":"10.1007\/978-3-540-88702-7"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_009","doi-asserted-by":"crossref","unstructured":"Ward Beullens, Thorsten Kleinjung and Frederik Vercauteren, CSI-FiSh: Efficient isogeny based signatures through class group computations, Cryptology ePrint Archive, Report 2019\/498 (2019).","DOI":"10.1007\/978-3-030-34578-5_9"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_010","doi-asserted-by":"crossref","unstructured":"Nicolas Bonifas and Daniel Dadush, Short paths on the Voronoi graph and the closest vector problem with preprocessing, in: SODA pp. 295\u2013314, 2015.","DOI":"10.1137\/1.9781611973730.22"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_011","doi-asserted-by":"crossref","unstructured":"Daniel Dadush, Oded Regev and Noah Stephens-Davidowitz, On the closest vector problem with a distance guarantee, in: CCC pp. 98\u2013109, 2014.","DOI":"10.1109\/CCC.2014.18"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_012","doi-asserted-by":"crossref","unstructured":"Emmanouil Doulgerakis, Thijs Laarhoven and Benne de Weger, Finding closest lattice vectors using approximate Voronoi cells, in: PQCrypto 2019.","DOI":"10.1007\/978-3-030-25510-7_1"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_013","doi-asserted-by":"crossref","unstructured":"L\u00e9o Ducas, Shortest vector from lattice sieving: a few dimensions for free, in: EUROCRYPT pp. 125\u2013145, 2018.","DOI":"10.1007\/978-3-319-78381-9_5"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_014","unstructured":"The European Telecommunications Standards Institute (ETSI), Quantum-Safe Cryptography 2019."},{"key":"2025120600293909882_j_jmc-2020-0074_ref_015","doi-asserted-by":"crossref","unstructured":"Ulrich Fincke and Michael Pohst, Improved methods for calculating vectors of short length in a lattice, Mathematics of Computation 44 (1985), 463\u2013471.","DOI":"10.1090\/S0025-5718-1985-0777278-8"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_016","doi-asserted-by":"crossref","unstructured":"Nicolas Gama, Phong Q. Nguy\u00ean and Oded Regev, Lattice enumeration using extreme pruning, in: EUROCRYPT pp. 257\u2013278, 2010.","DOI":"10.1007\/978-3-642-13190-5_13"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_017","doi-asserted-by":"crossref","unstructured":"Guillaume Hanrot and Damien Stehl\u00e9, Improved analysis of Kannan\u2019s shortest lattice vector algorithm, in: CRYPTO pp. 170\u2013186, 2007.","DOI":"10.1007\/978-3-540-74143-5_10"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_018","doi-asserted-by":"crossref","unstructured":"Gottfried Herold, Elena Kirshanova and Thijs Laarhoven, Speed-ups and time-memory trade-offs for tuple lattice sieving, in: PKC pp. 407\u2013436, 2018.","DOI":"10.1007\/978-3-319-76578-5_14"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_019","doi-asserted-by":"crossref","unstructured":"Ravi Kannan, Improved algorithms for integer programming and related lattice problems, in: STOC pp. 193\u2013206, 1983.","DOI":"10.1145\/800061.808749"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_020","doi-asserted-by":"crossref","unstructured":"Thijs Laarhoven, Sieving for shortest vectors in lattices using angular locality-sensitive hashing, in: CRYPTO pp. 3\u201322, 2015.","DOI":"10.1007\/978-3-662-47989-6_1"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_021","doi-asserted-by":"crossref","unstructured":"Thijs Laarhoven, Sieving for closest lattice vectors (with preprocessing), in: SAC pp. 523\u2013542, 2016.","DOI":"10.1007\/978-3-319-69453-5_28"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_022","doi-asserted-by":"crossref","unstructured":"Thijs Laarhoven and Artur Mariano, Progressive lattice sieving, in: PQCrypto pp. 292\u2013311, 2018.","DOI":"10.1007\/978-3-319-79063-3_14"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_023","doi-asserted-by":"crossref","unstructured":"Thijs Laarhoven, Michele Mosca and Joop van de Pol, Finding shortest lattice vectors faster using quantum search, Designs, Codes and Cryptography 77 (2015), 375\u2013400.","DOI":"10.1007\/s10623-015-0067-5"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_024","doi-asserted-by":"crossref","unstructured":"Daniele Micciancio, The hardness of the closest vector problem with preprocessing, IEEE Transactions on Information Theory 47 (2001), 1212\u20131215.","DOI":"10.1109\/18.915688"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_025","doi-asserted-by":"crossref","unstructured":"Daniele Micciancio and Panagiotis Voulgaris, A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations, in: STOC pp. 351\u2013358, 2010.","DOI":"10.1145\/1806689.1806739"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_026","doi-asserted-by":"crossref","unstructured":"Daniele Micciancio and Panagiotis Voulgaris, Faster exponential time algorithms for the shortest vector problem, in: SODA pp. 1468\u20131480, 2010.","DOI":"10.1137\/1.9781611973075.119"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_027","doi-asserted-by":"crossref","unstructured":"Daniele Micciancio and Michael Walter, Fast lattice point enumeration with minimal overhead, in: SODA pp. 276\u2013294, 2015.","DOI":"10.1137\/1.9781611973730.21"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_028","doi-asserted-by":"crossref","unstructured":"Phong Q. Nguy\u00ean and Thomas Vidick, Sieve algorithms for the shortest vector problem are practical, Journal ofMathematical Cryptology 2 (2008), 181\u2013207.","DOI":"10.1515\/JMC.2008.009"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_029","unstructured":"The National Institute of Standards and Technology (NIST), Post-Quantum Cryptography 2017."},{"key":"2025120600293909882_j_jmc-2020-0074_ref_030","doi-asserted-by":"crossref","unstructured":"Alice Pellet-Mary, Guillaume Hanrot and Damien Stehl\u00e9, Approx-SVP in ideal lattices with pre-processing, in: EUROCRYPT pp. 685\u2013716, 2019.","DOI":"10.1007\/978-3-030-17656-3_24"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_031","doi-asserted-by":"crossref","unstructured":"Peter Pivovarov, Volume thresholds for Gaussian and spherical random polytopes and their duals, Studia Mathematica 183 (2007), 15\u201334.","DOI":"10.4064\/sm183-1-2"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_032","unstructured":"Peter Pivovarov, Volume distribution and the geometry of high-dimensional random polytopes Ph.D. thesis, 2010."},{"key":"2025120600293909882_j_jmc-2020-0074_ref_033","doi-asserted-by":"crossref","unstructured":"Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, in: STOC pp. 84\u201393, 2005.","DOI":"10.1145\/1060590.1060603"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_034","doi-asserted-by":"crossref","unstructured":"Claude E. Shannon, Probability of error for optimal codes in a Gaussian channel, Bell System Technical Journal 38 (1959), 611\u2013656.","DOI":"10.1002\/j.1538-7305.1959.tb03905.x"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_035","doi-asserted-by":"crossref","unstructured":"Maria Shcherbina and Brunello Tirozzi, On the volume of the intersection of a sphere with random half spaces, Comptes Rendus Mathematique 334 (2002), 803\u2013806.","DOI":"10.1016\/S1631-073X(02)02345-2"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_036","doi-asserted-by":"crossref","unstructured":"Peter W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in: FOCS pp. 124\u2013134, 1994.","DOI":"10.1109\/SFCS.1994.365700"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_037","doi-asserted-by":"crossref","unstructured":"Naftali Sommer, Meir Feder and Ofir Shalvi, Finding the closest lattice point by iterative slicing, SIAM Journal of Discrete Mathematics 23 (2009), 715\u2013731.","DOI":"10.1137\/060676362"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_038","doi-asserted-by":"crossref","unstructured":"Damien Stehl\u00e9, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa, Efficient public key encryption based on ideal lattices, in: ASIACRYPT pp. 617\u2013635, 2009.","DOI":"10.1007\/978-3-642-10366-7_36"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_039","unstructured":"Noah Stephens-Davidowitz, A time-distance trade-off for GDD with preprocessing - Instantiating the DLW heuristic, in: CCC 2019."},{"key":"2025120600293909882_j_jmc-2020-0074_ref_040","doi-asserted-by":"crossref","unstructured":"Michel Talagrand, Intersecting random half-spaces: toward the Gardner\u2013Derrida formula, The Annals of Probability 28 (2000), 725\u2013758.","DOI":"10.1214\/aop\/1019160259"},{"key":"2025120600293909882_j_jmc-2020-0074_ref_041","unstructured":"Nicola Turchi, High-dimensional asymptotics for random polytopes Ph.D. thesis, 2019."},{"key":"2025120600293909882_j_jmc-2020-0074_ref_042","doi-asserted-by":"crossref","unstructured":"J. G. Wendel, A problem in geometric probability, Mathematica Scandinavica 11 (1962), 109\u2013112.","DOI":"10.7146\/math.scand.a-10655"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/15\/1\/article-p60.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0074\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0074\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:30:50Z","timestamp":1764981050000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0074\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,17]]},"references-count":42,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,11,17]]},"published-print":{"date-parts":[[2020,11,17]]}},"alternative-id":["10.1515\/jmc-2020-0074"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2020-0074","relation":{},"ISSN":["1862-2984"],"issn-type":[{"value":"1862-2984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,17]]}}}