## CryptoDB

### Paper: Estimating quantum speedups for lattice sieves

Authors: Martin R. Albrecht Vlad Gheorghiu Eamonn W. Postlethwaite John M. Schanck DOI: 10.1007/978-3-030-64834-3_20 Search ePrint Search Google Quantum variants of lattice sieve algorithms are routinely used to assess the security of lattice based cryptographic constructions. In this work we provide a heuristic, non-asymptotic, analysis of the cost of several algorithms for near neighbour search on high dimensional spheres. These algorithms are key components of lattice sieves. We design quantum circuits for near neighbour search algorithms and provide software that numerically optimises algorithm parameters according to various cost metrics. Using this software we estimate the cost of classical and quantum near neighbour search on spheres. For the most performant near neighbour search algorithm that we analyse we fi nd a small quantum speedup in dimensions of cryptanalytic interest. Achieving this speedup requires several optimistic physical and algorithmic assumptions.
##### BibTeX
@article{asiacrypt-2020-30652,
title={Estimating quantum speedups for lattice sieves},
booktitle={Advances in Cryptology - ASIACRYPT 2020},
publisher={Springer},
doi={10.1007/978-3-030-64834-3_20},
author={Martin R. Albrecht and Vlad Gheorghiu and Eamonn W. Postlethwaite and John M. Schanck},
year=2020
}