{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:44:05Z","timestamp":1765961045386,"version":"3.40.3"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319790626"},{"type":"electronic","value":"9783319790633"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-79063-3_22","type":"book-chapter","created":{"date-parts":[[2018,3,31]],"date-time":"2018-03-31T14:23:38Z","timestamp":1522506218000},"page":"467-486","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Quantum Collision-Finding in\u00a0Non-uniform Random Functions"],"prefix":"10.1007","author":[{"given":"Marko","family":"Balogh","sequence":"first","affiliation":[]},{"given":"Edward","family":"Eaton","sequence":"additional","affiliation":[]},{"given":"Fang","family":"Song","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,1]]},"reference":[{"key":"22_CR1","unstructured":"Password hashing competition (2012). https:\/\/password-hashing.net\/"},{"key":"22_CR2","unstructured":"National Institute of Standards and Technology. SHA-3 standard: permutation-based hash and extendable-output functions (2014). http:\/\/csrc.nist.gov\/publications\/drafts\/fips-202\/fips_202_draft.pdf"},{"key":"22_CR3","unstructured":"IBM Q quantum experience (2017). https:\/\/www.research.ibm.com\/ibm-q\/"},{"key":"22_CR4","unstructured":"National Institute of Standards and Technology. FIPS 180\u20131: secure hash standard, April 1995"},{"key":"22_CR5","unstructured":"People of ACM - John Martinis, 16 May 2017. https:\/\/www.acm.org\/articles\/people-of-acm\/2017\/john-martinis"},{"issue":"4","key":"22_CR6","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/1008731.1008735","volume":"51","author":"S Aaronson","year":"2004","unstructured":"Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM (JACM) 51(4), 595\u2013605 (2004)","journal-title":"J. ACM (JACM)"},{"issue":"3","key":"22_CR7","doi-asserted-by":"publisher","first-page":"37","DOI":"10.4086\/toc.2005.v001a003","volume":"1","author":"A Ambainis","year":"2005","unstructured":"Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range. Theory Comput. 1(3), 37\u201346 (2005). http:\/\/www.theoryofcomputing.org\/articles\/v001a003","journal-title":"Theory Comput."},{"issue":"1","key":"22_CR8","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A Ambainis","year":"2007","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210\u2013239 (2007). Preliminary version in FOCS 2004. arXiv:quant-ph\/0311001","journal-title":"SIAM J. Comput."},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Rosmanis, A., Unruh, D.: Quantum attacks on classical proof systems (the hardness of quantum rewinding). In: FOCS 2014, pp. 474\u2013483. IEEE, October 2014. Preprint on IACR ePrint 2014\/296","DOI":"10.1109\/FOCS.2014.57"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.: Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. arXiv preprint arXiv:1603.09383 (2016)","DOI":"10.1007\/978-3-319-69453-5_18"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 62\u201373. ACM (1993)","DOI":"10.1145\/168588.168596"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/BFb0053428","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 1994","author":"M Bellare","year":"1995","unstructured":"Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92\u2013111. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/BFb0053428"},{"key":"22_CR13","unstructured":"Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: The Keccak sponge function family (2007). http:\/\/keccak.noekeon.org\/"},{"key":"22_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-25385-0_3","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"D Boneh","year":"2011","unstructured":"Boneh, D., Dagdelen, \u00d6., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41\u201369. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-25385-0_3"},{"key":"22_CR15","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. arXiv preprint arXiv:quant-ph\/9605034 (1996)"},{"key":"22_CR16","unstructured":"Brassard, G., Hoyer, P., Tapp, A.: Quantum algorithm for the collision problem. arXiv preprint arXiv:quant-ph\/9705002 (1997)"},{"key":"22_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-642-25385-0_22","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"C Cr\u00e9peau","year":"2011","unstructured":"Cr\u00e9peau, C., Salvail, L., Simard, J.-R., Tapp, A.: Two provers in isolation. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 407\u2013430. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-25385-0_22"},{"key":"22_CR18","unstructured":"Czajkowski, J., Bruinderink, L.G., H\u00fclsing, A., Schaffner, C., Unruh, D.: Post-quantum security of the sponge construction. Cryptology ePrint Archive, Report 2017\/771 (2017). https:\/\/eprint.iacr.org\/2017\/771"},{"key":"22_CR19","unstructured":"Eaton, E., Song, F.: Making existential-unforgeable signatures strongly unforgeable in the quantum random-oracle model. In: 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2015. LIPIcs, vol. 44, pp. 147\u2013162. Schloss Dagstuhl (2015)"},{"key":"22_CR20","unstructured":"Ebrahimi, E., Unruh, D.: Quantum collision-resistance of non-uniformly distributed functions: upper and lower bounds. Cryptology ePrint Archive, Report 2017\/575 (2017)"},{"issue":"1","key":"22_CR21","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/s00145-011-9114-1","volume":"26","author":"E Fujisaki","year":"2013","unstructured":"Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. J. Cryptol. 26(1), 80\u2013101 (2013). Preliminary version in CRYPTO 1999","journal-title":"J. Cryptol."},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212\u2013219. ACM (1996)","DOI":"10.1145\/237814.237866"},{"key":"22_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-642-22792-9_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"S Hallgren","year":"2011","unstructured":"Hallgren, S., Smith, A., Song, F.: Classical cryptographic protocols in a quantum world. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 411\u2013428. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22792-9_23"},{"key":"22_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-662-49384-7_15","volume-title":"Public-Key Cryptography \u2013 PKC 2016","author":"A H\u00fclsing","year":"2016","unstructured":"H\u00fclsing, A., Rijneveld, J., Song, F.: Mitigating multi-target attacks in hash-based signatures. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9614, pp. 387\u2013416. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49384-7_15"},{"key":"22_CR25","unstructured":"Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008). https:\/\/bitcoin.org\/bitcoin.pdf"},{"key":"22_CR26","doi-asserted-by":"crossref","unstructured":"Rivest, R.L.: RFC 1321: the MD5 message-digest algorithm, April 1992. https:\/\/www.ietf.org\/rfc\/rfc1321.txt","DOI":"10.17487\/rfc1321"},{"issue":"5","key":"22_CR27","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"key":"22_CR28","unstructured":"Song, F.: Early days following Grover\u2019s quantum search algorithm. arXiv preprint arXiv:1709.01236 (2017)"},{"key":"22_CR29","doi-asserted-by":"crossref","unstructured":"Stevens, M., Bursztein, E., Karpman, P., Albertini, A., Markov, Y.: The first collision for full SHA-1. Cryptology ePrint Archive, Report 2017\/190 (2017). https:\/\/shattered.io\/","DOI":"10.1007\/978-3-319-63688-7_19"},{"key":"22_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/978-3-319-29360-8_6","volume-title":"Post-Quantum Cryptography","author":"EE Targhi","year":"2016","unstructured":"Targhi, E.E., Tabia, G.N., Unruh, D.: Quantum collision-resistance of non-uniformly distributed functions. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 79\u201385. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-29360-8_6"},{"key":"22_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-662-53644-5_8","volume-title":"Theory of Cryptography","author":"EE Targhi","year":"2016","unstructured":"Targhi, E.E., Unruh, D.: Post-quantum security of the Fujisaki-Okamoto and OAEP transforms. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 192\u2013216. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_8"},{"key":"22_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/978-3-662-49896-5_18","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"D Unruh","year":"2016","unstructured":"Unruh, D.: Computationally binding quantum commitments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 497\u2013527. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_18"},{"issue":"1","key":"22_CR33","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1137\/060670997","volume":"39","author":"J Watrous","year":"2009","unstructured":"Watrous, J.: Zero-knowledge against quantum attacks. SIAM J. Comput. 39(1), 25\u201358 (2009). Preliminary version in STOC 2006","journal-title":"SIAM J. Comput."},{"key":"22_CR34","unstructured":"Wiener, M.J.: Bounds on birthday attack times. Cryptology ePrint Archive, Report 2005\/318 (2005). http:\/\/eprint.iacr.org\/2005\/318"},{"issue":"13\u201314","key":"22_CR35","first-page":"1089","volume":"14","author":"H Yuen","year":"2014","unstructured":"Yuen, H.: A quantum lower bound for distinguishing random functions from random permutations. Quantum Inf. Comput. 14(13\u201314), 1089\u20131097 (2014)","journal-title":"Quantum Inf. Comput."},{"key":"22_CR36","doi-asserted-by":"crossref","unstructured":"Zhandry, M.: How to construct quantum random functions. In: FOCS 2012, pp. 679\u2013687. IEEE (2012). http:\/\/eprint.iacr.org\/2012\/182","DOI":"10.1109\/FOCS.2012.37"},{"issue":"7 & 8","key":"22_CR37","first-page":"557","volume":"15","author":"M Zhandry","year":"2015","unstructured":"Zhandry, M.: A note on the quantum collision and set equality problems. Quantum Inf. Comput. 15(7 & 8), 557\u2013567 (2015)","journal-title":"Quantum Inf. Comput."},{"key":"22_CR38","doi-asserted-by":"crossref","unstructured":"Zhandry, M.: Secure identity-based encryption in the quantum random oracle model. Int. J. Quantum Inf. 13(4) (2015). Early version in Crypto 2012. http:\/\/eprint.iacr.org\/2012\/076","DOI":"10.1142\/S0219749915500148"}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-79063-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T14:33:39Z","timestamp":1710340419000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-79063-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319790626","9783319790633"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-79063-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"1 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PQCrypto","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Post-Quantum Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fort Lauderdale","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pqcrypto2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.math.fau.edu\/pqcrypto2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}