Quantum algorithms for the subset-sum problem

Daniel J.  Bernstein; Stacey Jeffery; Tanja Lange; Alexander Meurer

Paper 2013/199

Quantum algorithms for the subset-sum problem

Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer

Abstract

This paper introduces a subset-sum algorithm with heuristic asymptotic cost exponent below 0.25. The new algorithm combines the 2010 Howgrave-Graham--Joux subset-sum algorithm with a new streamlined data structure for quantum walks on Johnson graphs.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. expanded version of PQCrypto 2013 paper
Keywords: subset sum quantum search quantum walks radix trees decoding SVP CVP
Contact author(s): tanja @ hyperelliptic org
History: 2013-04-09: received
Short URL: https://ia.cr/2013/199
License: CC BY

BibTeX

@misc{cryptoeprint:2013/199,
      author = {Daniel J.  Bernstein and Stacey Jeffery and Tanja Lange and Alexander Meurer},
      title = {Quantum algorithms for the subset-sum problem},
      howpublished = {Cryptology ePrint Archive, Paper 2013/199},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/199}},
      url = {https://eprint.iacr.org/2013/199}
}