English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Lattice-based cryptography has recently emerged as a prime candidate forefficient and secure post-quantum cryptography. The two main hard problemsunderlying its security are the shortest vector problem (SVP) and the closestvector problem (CVP). Various algorithms have been studied for solving theseproblems, and for SVP, lattice sieving currently dominates in terms of theasymptotic time complexity: one can heuristically solve SVP in time$2^{0.292d}$ in high dimensions $d$ [BDGL'16]. Although several SVP algorithmscan also be used to solve CVP, it is not clear whether this also holds forheuristic lattice sieving methods. The best time complexity for CVP iscurrently $2^{0.377d}$ [BGJ'14].  In this paper we revisit sieving algorithms for solving SVP, and study howthese algorithms can be modified to solve CVP and its variants as well. Ourfirst method is aimed at solving one problem instance and minimizes the overalltime complexity for a single CVP instance with a time complexity of$2^{0.292d}$. Our second method minimizes the amortized time complexity forseveral instances on the same lattice, at the cost of a larger preprocessingcost. We can solve the closest vector problem with preprocessing (CVPP) with$2^{0.636d}$ space and preprocessing, in $2^{0.136d}$ time, while the querycomplexity can even be reduced to $2^{\epsilon d}$ at the cost of preprocessingtime and memory complexities of $(1/\epsilon)^{O(d)}$.  For easier variants of CVP, such as approximate CVP and bounded distancedecoding (BDD), we further show how the preprocessing method achieves evenbetter complexities. For instance, we can solve approximate CVPP with largeapproximation factors $k$ with polynomial-sized advice in polynomial time if $k= \Omega(\sqrt{d/\log d})$, heuristically closing the gap between thedecision-CVPP result of [AR'04] and the search-CVPP result of [DRS'14].

Sieving for closest lattice vectors (with preprocessing)