Paper 2019/1016

Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice Sieving

Elena Kirshanova, Erik Mårtensson, Eamonn W. Postlethwaite, and Subhayan Roy Moulik

Abstract

The Shortest Vector Problem (SVP) is one of the mathematical foundations of lattice based cryptography. Lattice sieve algorithms are amongst the foremost methods of solving SVP. The asymptotically fastest known classical and quantum sieves solve SVP in a \(d\)-dimensional lattice in \(2^{cd + o(d)}\) time steps with \(2^{c'd + o(d)}\) memory for constants \(c, c'\). In this work, we give various quantum sieving algorithms that trade computational steps for memory. We first give a quantum analogue of the classical \(k\)-Sieve algorithm [Herold--Kirshanova--Laarhoven, PKC'18] in the Quantum Random Access Memory (QRAM) model, achieving an algorithm that heuristically solves SVP in \(2^{0.2989d + o(d)}\) time steps using \(2^{0.1395d + o(d)}\) memory. This should be compared to the state-of-the-art algorithm [Laarhoven, Ph.D Thesis, 2015] which, in the same model, solves SVP in \(2^{0.2653d + o(d)}\) time steps and memory. In the QRAM model these algorithms can be implemented using \(poly(d)\) width quantum circuits. Secondly, we frame the \(k\)-Sieve as the problem of \(k\)-clique listing in a graph and apply quantum \(k\)-clique finding techniques to the \(k\)-Sieve. Finally, we explore the large quantum memory regime by adapting parallel quantum search [Beals et al., Proc. Roy. Soc. A'13] to the \(2\)-Sieve and giving an analysis in the quantum circuit model. We show how to heuristically solve SVP in \(2^{0.1037d + o(d)}\) time steps using \(2^{0.2075d + o(d)}\) quantum memory.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in ASIACRYPT 2019
Keywords
approximate k-list problemcryptanalysisdistributed computationgrover's algorithmlattice sievingnearest neighbour algorithmsquantum cryptographyshortest vector problemSVP
Contact author(s)
eamonn postlethwaite 2016 @ rhul ac uk
History
2019-09-10: received
Short URL
https://ia.cr/2019/1016
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1016,
      author = {Elena Kirshanova and Erik Mårtensson and Eamonn W.  Postlethwaite and Subhayan Roy Moulik},
      title = {Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice Sieving},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1016},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1016}},
      url = {https://eprint.iacr.org/2019/1016}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.