Quantum algorithms for the subset-sum problem

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

Paper 2013/199 Original: eprint.iacr.org/2013/199 ↗

Quantum algorithms for the subset-sum problem

Daniel J. Bernstein

Stacey Jeffery

Tanja Lange

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: Preprint.
History: 2013-04-09: last updated; 2013-04-09: published
Short URL: https://ia.cr/2013/199
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2013/199}
}