Quantum algorithms for the subset-sum problem

D.J. Bernstein; S. Jeffery; T. Lange; A. Meurer

doi:10.1007/978-3-642-38616-9_2

Quantum algorithms for the subset-sum problem

D.J. Bernstein
, S. Jeffery
, T. Lange
, A. Meurer

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

54 Citations (Scopus)

1 Downloads (Pure)

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. Keywords: subset sum; quantum search; quantum walks; radix trees; decoding; SVP; CVP

Original language	English
Title of host publication	Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings)
Editors	Ph. Gaborit
Place of Publication	Berlin
Publisher	Springer
Pages	16-33
ISBN (Print)	978-3-642-38615-2
DOIs	https://doi.org/10.1007/978-3-642-38616-9_2
Publication status	Published - 2013
Event	5th International Conference on Post-Quantum Cryptography (PQCrypto 2013) - Limoges, France Duration: 4 Jun 2013 → 7 Jun 2013 Conference number: 5 http://pqcrypto2013.xlim.fr/

Publication series

Name	Lecture Notes in Computer Science
Volume	7932
ISSN (Print)	0302-9743

Conference

Conference	5th International Conference on Post-Quantum Cryptography (PQCrypto 2013)
Abbreviated title	PQCrypto 2013
Country/Territory	France
City	Limoges
Period	4/06/13 → 7/06/13
Internet address	http://pqcrypto2013.xlim.fr/

Access to Document

10.1007/978-3-642-38616-9_2

http://eprint.iacr.org/2013/199

Cite this

@inproceedings{2fd5e09c5bcb478b89ee618d5e7d6d67,

title = "Quantum algorithms for the subset-sum problem",

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. Keywords: subset sum; quantum search; quantum walks; radix trees; decoding; SVP; CVP",

author = "D.J. Bernstein and S. Jeffery and T. Lange and A. Meurer",

year = "2013",

doi = "10.1007/978-3-642-38616-9\_2",

language = "English",

isbn = "978-3-642-38615-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "16--33",

editor = "Ph. Gaborit",

booktitle = "Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings)",

address = "Germany",

note = "5th International Conference on Post-Quantum Cryptography (PQCrypto 2013), PQCrypto 2013 ; Conference date: 04-06-2013 Through 07-06-2013",

url = "http://pqcrypto2013.xlim.fr/",

}

Bernstein, DJ, Jeffery, S, Lange, T & Meurer, A 2013, Quantum algorithms for the subset-sum problem. in P Gaborit (ed.), Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings). Lecture Notes in Computer Science, vol. 7932, Springer, Berlin, pp. 16-33, 5th International Conference on Post-Quantum Cryptography (PQCrypto 2013), Limoges, France, 4/06/13. https://doi.org/10.1007/978-3-642-38616-9_2

Quantum algorithms for the subset-sum problem. / Bernstein, D.J.; Jeffery, S.; Lange, T. et al.
Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings). ed. / Ph. Gaborit. Berlin: Springer, 2013. p. 16-33 (Lecture Notes in Computer Science; Vol. 7932).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Quantum algorithms for the subset-sum problem

AU - Bernstein, D.J.

AU - Jeffery, S.

AU - Lange, T.

AU - Meurer, A.

N1 - Conference code: 5

PY - 2013

Y1 - 2013

N2 - 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. Keywords: subset sum; quantum search; quantum walks; radix trees; decoding; SVP; CVP

AB - 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. Keywords: subset sum; quantum search; quantum walks; radix trees; decoding; SVP; CVP

U2 - 10.1007/978-3-642-38616-9_2

DO - 10.1007/978-3-642-38616-9_2

M3 - Conference contribution

SN - 978-3-642-38615-2

T3 - Lecture Notes in Computer Science

SP - 16

EP - 33

BT - Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings)

A2 - Gaborit, Ph.

PB - Springer

CY - Berlin

T2 - 5th International Conference on Post-Quantum Cryptography (PQCrypto 2013)

Y2 - 4 June 2013 through 7 June 2013

ER -

Quantum algorithms for the subset-sum problem

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this