Quantum algorithms for the subset-sum problem

You are looking at a specific version 20130409:050745 of this paper. See the latest version.

Paper 2013/199

Quantum algorithms for the subset-sum problem

Daniel J. Bernstein and Stacey Jeffery and 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