Approximate Voronoi cells for lattices, revisited
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–Laarhoven–De Weger [PQCrypto, 2019] of determining exact asymptotics on the volume of these Voronoi cells under...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2020-11-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2020-0074 |
| _version_ | 1818474262101491712 |
|---|---|
| author | Laarhoven Thijs |
| author_facet | Laarhoven Thijs |
| author_sort | Laarhoven Thijs |
| collection | DOAJ |
| description | 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–Laarhoven–De 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 20.076d+o(d)$2^{0.076d + o(d)}$ memory, and we show how to obtain time–memory trade-offs even when using less than 20.048d+o(d)$2^{0.048d + o(d)}$ 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 dd/2+o(d)$d^{d/2 + o(d)}$ matching worst-case enumeration bounds, and achieving the same asymptotic scaling as average-case enumeration algorithms for the closest vector problem. |
| first_indexed | 2024-04-14T04:35:01Z |
| format | Article |
| id | doaj.art-71c5153999b34d57a54a9e47b6d11740 |
| institution | Directory Open Access Journal |
| issn | 1862-2984 |
| language | English |
| last_indexed | 2024-04-14T04:35:01Z |
| publishDate | 2020-11-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-71c5153999b34d57a54a9e47b6d117402022-12-22T02:11:54ZengDe GruyterJournal of Mathematical Cryptology1862-29842020-11-01151607110.1515/jmc-2020-0074jmc-2020-0074Approximate Voronoi cells for lattices, revisitedLaarhoven Thijs0Eindhoven University of Technology, Eindhoven, The NetherlandsWe 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–Laarhoven–De 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 20.076d+o(d)$2^{0.076d + o(d)}$ memory, and we show how to obtain time–memory trade-offs even when using less than 20.048d+o(d)$2^{0.048d + o(d)}$ 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 dd/2+o(d)$d^{d/2 + o(d)}$ matching worst-case enumeration bounds, and achieving the same asymptotic scaling as average-case enumeration algorithms for the closest vector problem.https://doi.org/10.1515/jmc-2020-0074voronoi cellspolytopesvolume estimationlatticesclosest vector problem11h0652b1152c0794a60 |
| spellingShingle | Laarhoven Thijs Approximate Voronoi cells for lattices, revisited Journal of Mathematical Cryptology voronoi cells polytopes volume estimation lattices closest vector problem 11h06 52b11 52c07 94a60 |
| title | Approximate Voronoi cells for lattices, revisited |
| title_full | Approximate Voronoi cells for lattices, revisited |
| title_fullStr | Approximate Voronoi cells for lattices, revisited |
| title_full_unstemmed | Approximate Voronoi cells for lattices, revisited |
| title_short | Approximate Voronoi cells for lattices, revisited |
| title_sort | approximate voronoi cells for lattices revisited |
| topic | voronoi cells polytopes volume estimation lattices closest vector problem 11h06 52b11 52c07 94a60 |
| url | https://doi.org/10.1515/jmc-2020-0074 |
| work_keys_str_mv | AT laarhoventhijs approximatevoronoicellsforlatticesrevisited |