You are looking at a specific version 20191007:082623 of this paper. See the latest version.

Paper 2019/1161

Quantum speedups for lattice sieves are tenuous at best

Martin R. Albrecht and Vlad Gheorghiu and Eamonn W. Postlethwaite and John M. Schanck

Abstract

Quantum variants of lattice sieve algorithms are often 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 used in lattice sieves. We design quantum circuits for near neighbour 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. We find that quantum search may provide a small speedup in dimensions of cryptanalytic interest, but only under exceedingly optimistic physical and algorithmic assumptions.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
lattice sievesquantum computingcryptanalysispost-quantum
Contact author(s)
eamonn postlethwaite 2016 @ rhul ac uk,vlad gheorghiu @ uwaterloo ca,jschanck @ uwaterloo ca,martin albrecht @ royalholloway ac uk
History
2020-09-14: last of 2 revisions
2019-10-07: received
See all versions
Short URL
https://ia.cr/2019/1161
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.