Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / subset sum, quantum search, quantum walks, radix trees, decoding, SVP, CVP

Publication Info: expanded version of PQCrypto 2013 paper

Date: received 7 Apr 2013

Contact author: tanja at hyperelliptic org

Available format(s): PDF | BibTeX Citation

Version: 20130409:050745 (All versions of this report)

Short URL: ia.cr/2013/199

Discussion forum: Show discussion | Start new discussion