{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T16:47:56Z","timestamp":1769100476976,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642386152","type":"print"},{"value":"9783642386169","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38616-9_2","type":"book-chapter","created":{"date-parts":[[2013,6,4]],"date-time":"2013-06-04T03:55:16Z","timestamp":1370318116000},"page":"16-33","source":"Crossref","is-referenced-by-count":38,"title":["Quantum Algorithms for the Subset-Sum Problem"],"prefix":"10.1007","author":[{"given":"Daniel J.","family":"Bernstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stacey","family":"Jeffery","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tanja","family":"Lange","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Meurer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","unstructured":"\u2014 (no editor): 20th annual symposium on foundations of computer science. IEEE Computer Society, New York (1979). MR 82a:68004. See [32]"},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A. Ambainis","year":"2007","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM Journal on Computing 37, 210\u2013239 (2007). http:\/\/arxiv.org\/abs\/quant-ph\/0311001 . Citations in this document: \u00a73, \u00a73, \u00a73","journal-title":"SIAM Journal on Computing"},{"key":"2_CR3","unstructured":"Becker, A., Coron, J.-S., Joux, A.: Improved generic algorithms for hard knapsacks. In: Eurocrypt 2011 [27] (2011). http:\/\/eprint.iacr.org\/2011\/474 . Citations in this document: \u00a71, \u00a71.1, \u00a71, \u00a74, \u00a75"},{"key":"2_CR4","unstructured":"Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in 2 n\/20: how 1 + 1 = 0 improves information set decoding. In: Eurocrypt 2012 [28] (2012). http:\/\/eprint.iacr.org\/2012\/026 . Citations in this document: \u00a71,\u00a71,\u00a71, \u00a71, \u00a75"},{"key":"2_CR5","unstructured":"Bernstein, D.J.: Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete? In: Workshop Record of SHARCS\u201909: Special-purpose Hardware for Attacking Cryptographic Systems (2009). http:\/\/cr.yp.to\/papers.html#collisioncost . Citations in this document: \u00a72"},{"key":"2_CR6","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M. Boyer","year":"1998","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte Der Physik 46, 493\u2013505 (1998). http:\/\/arxiv.org\/abs\/quant-ph\/9605034v1 . Citations in this document: \u00a72, \u00a72","journal-title":"Fortschritte Der Physik"},{"key":"2_CR7","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: [20], pp. 53\u201374 (2002). http:\/\/arxiv.org\/abs\/quant-ph\/0005055 . Citations in this document: x4 Quantum Algorithms for the Subset-sum Problem 33"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, G., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: LATIN\u201998 [21], pp. 163\u2013169 (1998). MR 99g:94013. Citations inthis document: \u00a72, \u00a72","DOI":"10.1007\/BFb0054319"},{"key":"2_CR9","first-page":"54","volume":"2","author":"W.-L. Chang","year":"2009","unstructured":"Chang, W.-L., Ren, T.-T., Feng, M., Lu, L.C., Lin, K.W., Guo, M.: Quantum algorithms of the subset-sum problem on a quantum computer. International Conference on Information Engineering 2, 54\u201357 (2009). Citations in this document: \u00a72","journal-title":"International Conference on Information Engineering"},{"key":"2_CR10","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1090\/S0025-5718-05-01805-3","volume":"75","author":"A.-S. Elsenhans","year":"2006","unstructured":"Elsenhans, A.-S., Jahnel, J.: The diophantine equation x4 + 2y4= z4+ 4w4. Mathematics of Computation 75, 935\u2013940 (2006). http:\/\/www.uni-math.gwdg.de\/jahnel\/linkstopaperse.html . Citations in this document: \u00a74","journal-title":"Mathematics of Computation"},{"key":"2_CR11","unstructured":"Elsenhans, A.-S., Jahnel, J.: The Diophantine equation x4 + 2y4 = z4 + 4w4\u2014 a number of improvements (2006). http:\/\/www.uni-math.gwdg.de\/jahnel\/linkstopaperse.html . Citations in this document: \u00a74"},{"key":"2_CR12","unstructured":"Gilbert, H. (ed.): Advances in cryptology\u2014EUROCRYPT 2010, 29th annual international conference on the theory and applications of cryptographic techniques, French Riviera, May 30-June 3, 2010, proceedings. LNCS, vol. 6110. Springer (2010). See [17]"},{"key":"2_CR13","unstructured":"Goldwasser, S. (ed.): 35th annual IEEE symposium on the foundations of computer science. Proceedings of the IEEE symposium held in Santa Fe, NM, November 20-22, 1994. IEEE (1994). ISBN 0-8186-6580-7. MR 98h:68008. See [30]"},{"key":"2_CR14","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: [26], pp. 212\u2013219 (1996). MR 1427516. http:\/\/arxiv.org\/abs\/quant-ph\/9605043"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"L.K. Grover","year":"1997","unstructured":"Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters 79, 325\u2013328 (1997). http:\/\/arxiv.org\/abs\/quant-ph\/9706033 . Citations in this document: \u00a72, \u00a72","journal-title":"Physical Review Letters"},{"key":"2_CR16","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E. Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsackproblem. Journal of the ACM 21, 277\u2013292 (1974). Citations in this document: \u00a72","journal-title":"Journal of the ACM"},{"key":"2_CR17","unstructured":"Howgrave-Graham, N., Joux, A.: New generic algorithms for hard knapsacks. In: Eurocrypt 2010 [12] (2010). http:\/\/eprint.iacr.org\/2010\/189 . Citations in this document: \u00a71, \u00a71, \u00a71, \u00a71, \u00a74, \u00a75, \u00a75, \u00a75"},{"key":"2_CR18","unstructured":"Johnson, D.S., Feige, U. (eds.): Proceedings of the 39th annual ACM symposium on the theory of computing, San Diego, California, USA, June 11-13, 2007. Association for Computing Machinery (2007). ISBN 978-1-59593-631-8. See [23]"},{"key":"2_CR19","unstructured":"Lee, D.H., Wang, X. (eds.): Advances in cryptology\u2014ASIACRYPT 2011, 17th international conference on the theory and application of cryptology and information security, Seoul, South Korea, December 4-8, 2011, proceedings. LNCS,vol. 7073. Springer (2011). ISBN 978-3-642-25384-3. See [24]"},{"key":"2_CR20","unstructured":"Lomonaco Jr., S.J., Brandt, H.E. (eds.): Quantum computation and information. Papers from the AMS Special Session held in Washington, DC, January 19-21, 2000. Contemporary Mathematics, vol. 305. American Mathematical Society(2002). ISBN 0-8218-2140-7. MR 2003g:81006. See [7]"},{"key":"2_CR21","unstructured":"Lucchesi, C.L., Moura, A.V. (eds.): LATIN\u201998: theoretical informatics. Proceedings of the 3rd Latin American symposium held in Campinas, April 20-24, 1998. LNCS, vol. 1380. Springer (1998). ISBN 3-540-64275-7. MR 99d:68007. See [8]"},{"key":"2_CR22","unstructured":"Lyubashevsky, V., Palacio, A., Segev, G.: Public-key cryptographic primitives provably as secure as subset sum. In: TCC 2010 [25], pp. 382\u2013400 (2010). http:\/\/eprint.iacr.org\/2009\/576 . Citations in this document: \u00a71, \u00a71"},{"key":"2_CR23","unstructured":"Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk.In: STOC 2007 [18], pp. 575\u2013584 (2007). http:\/\/arxiv.org\/abs\/quant-ph\/0608026 . Citations in this document: \u00a73"},{"key":"2_CR24","unstructured":"May, A., Meurer, A., Thomae, E.: Decoding random linear codes in \u00d5(20:054n).In: Asiacrypt 2011 [19] (2011). http:\/\/www.cits.rub.de\/imperia\/md\/content\/may\/paper\/decoding.pdf . Citations in this document: \u00a71, \u00a71, \u00a71"},{"key":"2_CR25","doi-asserted-by":"crossref","unstructured":"Micciancio, D. (ed.): Theory of cryptography, 7th theory of cryptography conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010, proceedings. LNCS,vol. 5978. Springer (2010). ISBN 978-3-642-11798-5. See [22]","DOI":"10.1007\/978-3-642-11799-2"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Miller, G.L. (ed.): Proceedings of the twenty-eighth annual ACM symposium on the theory of computing, Philadelphia, PA, May 22-24, 1996. Association for Computing Machinery (1996). ISBN 0-89791-785-5. MR 97g:68005. See [14]","DOI":"10.1145\/237814"},{"key":"2_CR27","unstructured":"Paterson, K.G. (ed.): Advances in cryptology\u2014EUROCRYPT 2011, 30th annual international conference on the theory and applications of cryptographic techniques, Tallinn, Estonia, May 15-19, 2011, proceedings. LNCS, vol. 6632. Springer (2011). ISBN 978-3-642-20464-7. See [3]"},{"key":"2_CR28","unstructured":"Pointcheval, D., Johansson, T. (eds.): Advances in cryptology\u2014EUROCRYPT2012\u201431st annual international conference on the theory and applications of cryptographic techniques, Cambridge, UK, April 15-19, 2012, proceedings. LNCS, vol. 7237. Springer (2012). ISBN 978-3-642-29010-7. See [4]"},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"Schroeppel, R., Shamir, A.: A T = O(2 n\/2), S = O(2 n\/4) algorithm for certain NP-complete problems. SIAM Journal on Computing 10, 456\u2013464 (1981). Citations in this document: \u00a74","DOI":"10.1137\/0210033"},{"key":"2_CR30","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: [13], pp. 124\u2013134 (1994); see also newer version [31]. MR 1489242"},{"key":"2_CR31","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26, 1484\u20131509 (1997); see also older version [30]. MR 98i:11108. http:\/\/arxiv.org\/abs\/quant-ph\/9508027"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Wegman, M.N., Lawrence Carter, J.: New classes and applications of hash functions. In: [1], pp. 175\u2013182 (1979); see also newer version [33]","DOI":"10.1109\/SFCS.1979.26"},{"key":"2_CR33","doi-asserted-by":"crossref","unstructured":"Wegman, M.N., Lawrence Carter, J.: New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences 22, 265\u2013279(1981); see also older version [32]. ISSN 0022-0000. MR 82i:68017. Citations inthis document: \u00a73","DOI":"10.1016\/0022-0000(81)90033-7"}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38616-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T17:33:56Z","timestamp":1645637636000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38616-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642386152","9783642386169"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38616-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}