Approximate Voronoi cells for lattices, revisited (Q2027268)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Approximate Voronoi cells for lattices, revisited
scientific article

    Statements

    Approximate Voronoi cells for lattices, revisited (English)
    0 references
    0 references
    25 May 2021
    0 references
    Lattice problems, such as the shortest and closest vector problems, remain difficult computationally even in the presence of a quantum computer. As such, these problems are of vital interest to cryptographers. The author examines the Voronoi cells approach to the closest vector problem. \textit{E. Doulgerakis} et al. [Lect. Notes Comput. Sci. 11505, 3--22 (2019; Zbl 1447.94033)] had given the problem of determining the exact asymptotics on the volume of Voronoi cells under the Guassian heuristic. The author solves this open problem and uses it to obtain improved upper bounds on the time complexity of the randomized iterative slicer. The author settles the open problem of obtaining a continuous trade off between the size of the advice and the query time complexity, since the time complexity with subexponential advice in this approach matches the worst case enumeration bounds and achieves the same asymptotic scaling as average case enumeration algorithms for the closest vector problem.
    0 references
    Voronoi cells
    0 references
    polytopes
    0 references
    volume estimation
    0 references
    lattices
    0 references
    closest vector problem
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references