Paper 2019/1161

Estimating quantum speedups for lattice sieves

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


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 find a small quantum speedup in dimensions of cryptanalytic interest. Achieving this speedup requires several optimistic physical and algorithmic assumptions.

Note: camera ready for ac2020 with embedded data and appendices

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
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
2020-09-14: last of 2 revisions
2019-10-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Martin R.  Albrecht and Vlad Gheorghiu and Eamonn W.  Postlethwaite and John M.  Schanck},
      title = {Estimating quantum speedups for lattice sieves},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1161},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.