Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Kirshanova, Elena ; Mårtensson, Erik LU orcid ; Postlethwaite, Eamonn and Roy Moulik, Subhayan (2019) Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security
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^{\const d + \smallo(d)}$ time steps with $2^{\const' d + \smallo(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... (More)
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^{\const d + \smallo(d)}$ time steps with $2^{\const' d + \smallo(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. (Less)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
shortest vector problem (SVP), lattice sieving, Grover's algorithm, approximate $k$-list problem, nearest neighbour algorithms, distributed computation
host publication
Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
publisher
Springer
conference name
Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security
conference location
Kobe, Japan
conference dates
2019-12-08 - 2019-12-12
external identifiers
  • scopus:85076686124
DOI
10.1007/978-3-030-34578-5_19
language
English
LU publication?
yes
id
6347ed9c-4195-4393-90b5-780761f2b614
alternative location
https://eprint.iacr.org/2019/1016
date added to LUP
2019-12-16 17:04:05
date last changed
2024-01-31 13:08:42
@inproceedings{6347ed9c-4195-4393-90b5-780761f2b614,
  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^{\const d + \smallo(d)}$ time steps with $2^{\const' d + \smallo(d)}$ memory for constants $c, c'$. In this work, we give various quantum sieving algorithms that trade computational steps for memory.<br/><br/>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.<br/><br/>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.<br/><br/> 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.}},
  author       = {{Kirshanova, Elena and Mårtensson, Erik and Postlethwaite, Eamonn and Roy Moulik, Subhayan}},
  booktitle    = {{Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings}},
  keywords     = {{shortest vector problem (SVP); lattice sieving; Grover's algorithm; approximate $k$-list problem; nearest neighbour algorithms; distributed computation}},
  language     = {{eng}},
  publisher    = {{Springer}},
  title        = {{Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving}},
  url          = {{http://dx.doi.org/10.1007/978-3-030-34578-5_19}},
  doi          = {{10.1007/978-3-030-34578-5_19}},
  year         = {{2019}},
}