#### Vol. 4, No. 1, 2020

 Recent Volumes 5: Gauge Theory and Low-Dimensional Topology 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index ISSN (electronic): 2329-907X ISSN (print): 2329-9061 MSP Books and Monographs Other MSP Publications
The nearest-colattice algorithm: Time-approximation tradeoff for approx-CVP

### Thomas Espitau and Paul Kirchner

Vol. 4 (2020), No. 1, 251–266
##### Abstract

We exhibit a hierarchy of polynomial time algorithms solving approximate variants of the closest vector problem (CVP). Our first contribution is a heuristic algorithm achieving the same distance tradeoff as HSVP algorithms, namely $\approx {\beta }^{n∕\left(2\beta \right)}covol{\left(\Lambda \right)}^{1∕n}$ for a random lattice $\Lambda$ of rank $n$. Compared to the so-called Kannan’s embedding technique, our algorithm allows the use of precomputations and can be used for efficient batch CVP instances. This implies that some attacks on lattice-based signatures lead to very cheap forgeries, after a precomputation. Our second contribution is a proven reduction from approximating the closest vector with a factor $\approx {n}^{3∕2}{\beta }^{3n∕\left(2\beta \right)}$ to the shortest vector problem (SVP) in dimension $\beta$.

##### Keywords
lattice, closest vector problem
##### Mathematical Subject Classification 2010
Primary: 11HXX, 68W40
##### Milestones
Received: 28 February 2020
Revised: 28 February 2020
Accepted: 29 April 2020
Published: 29 December 2020
##### Authors
 Thomas Espitau NTT Corporation Tokyo Japan Paul Kirchner Rennes University Rennes France