{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T16:22:49Z","timestamp":1761582169104,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,2,6]],"date-time":"2022-02-06T00:00:00Z","timestamp":1644105600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,6]],"date-time":"2022-02-06T00:00:00Z","timestamp":1644105600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NTT Laboratories"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2022,3]]},"abstract":"Abstract<\/jats:title>In this paper, we analyze the security of subset-resilient hash function families, which is first proposed as a requirement of a hash-based signature scheme called HORS. Let $${\\mathcal {H}}$$<\/jats:tex-math>\n H<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be a family of functions mapping an element to a subset of size at most k<\/jats:italic>. (r<\/jats:italic>,\u00a0k<\/jats:italic>)-subset resilience guarantees that given a random function H<\/jats:italic> from $${\\mathcal {H}}$$<\/jats:tex-math>\n H<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, it is hard to find an $$(r+1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n r<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-tuple $$(x,x_1,\\ldots ,x_r)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n x<\/mml:mi>\n ,<\/mml:mo>\n \n x<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n x<\/mml:mi>\n r<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that (1) H<\/jats:italic>(x<\/jats:italic>) is covered by the union of $$H(x_i)$$<\/jats:tex-math>\n \n H<\/mml:mi>\n (<\/mml:mo>\n \n x<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and (2) x<\/jats:italic> is not equal to any $$x_i$$<\/jats:tex-math>\n \n x<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Subset resilience and its variants are related to nearly all existing stateless hash-based signature schemes, but the power of this security notion is lacking in research. We present three results on subset resilience. First, we show a generic quantum attack against subset resilience, whose time complexity is smaller than simply implementing Grover\u2019s search. Second, we show that subset-resilient hash function families imply the existence of distributional collision-resistant hash function families. Informally, distributional collision resistance is a relaxation of collision resistance, which guarantees that it is hard to find a uniform<\/jats:italic> collision for a hash function. This result implies a comparison among the power of subset resilience, collision resistance, and distributional collision resistance. Third, we prove the fully black-box separation from one-way permutations.<\/jats:p>","DOI":"10.1007\/s10623-022-01008-4","type":"journal-article","created":{"date-parts":[[2022,2,6]],"date-time":"2022-02-06T16:02:16Z","timestamp":1644163336000},"page":"719-758","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On subset-resilient hash function families"],"prefix":"10.1007","volume":"90","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8367-389X","authenticated-orcid":false,"given":"Quan","family":"Yuan","sequence":"first","affiliation":[]},{"given":"Mehdi","family":"Tibouchi","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Abe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,6]]},"reference":[{"issue":"4","key":"1008_CR1","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":"1","key":"1008_CR2","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).","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1008_CR3","doi-asserted-by":"publisher","first-page":"2117","DOI":"10.1137\/15M1034064","volume":"45","author":"G Asharov","year":"2016","unstructured":"Asharov G., Segev G.: Limits on the power of indistinguishability obfuscation and functional encryption. SIAM J. Comput. 45(6), 2117\u20132176 (2016).","journal-title":"SIAM J. Comput."},{"key":"1008_CR4","unstructured":"Aumasson J.-P., Endignoux G.: Clarifying the subset-resilience problem. Cryptology ePrint Archive, Report 2017\/909 (2017)."},{"key":"1008_CR5","doi-asserted-by":"crossref","unstructured":"Aumasson J.-P., Endignoux G.: Improving stateless hash-based signatures. In: Topics in Cryptology: CT-RSA 2018, Vol. 10808 of LNCS. Springer, Berlin, pp. 219\u2013242 (2018).","DOI":"10.1007\/978-3-319-76953-0_12"},{"key":"1008_CR6","doi-asserted-by":"crossref","unstructured":"Belovs A.: Learning-graph-based quantum algorithm for k-distinctness. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, IEEE, pp. 207\u2013216 (2012).","DOI":"10.1109\/FOCS.2012.18"},{"key":"1008_CR7","doi-asserted-by":"crossref","unstructured":"Berman I., Degwekar A., Rothblum R.D., Vasudevan P.N.: Multi-collision resistant hash functions and their applications. In: Advances in Cryptology: EUROCRYPT 2018, Vol. 10821 of LNCS. Springer, pp. 133\u2013161 (2018).","DOI":"10.1007\/978-3-319-78375-8_5"},{"key":"1008_CR8","doi-asserted-by":"crossref","unstructured":"Bernstein D.J., Hopwood, D., H\u00fclsing, A., Lange T., Niederhagen R., Papachristodoulou L., Schwabe M.S., Wilcox-O\u2019Hearn Z.: SPHINCS: Practical stateless hash-based signatures. In: Advances in Cryptology: EUROCRYPT 2015, Vol. 9056 of LNCS. Springer, Berlin, pp. 368\u2013397 (2015).","DOI":"10.1007\/978-3-662-46800-5_15"},{"key":"1008_CR9","unstructured":"Bernstein D.J., H\u00fclsing A., K\u00f6lbl S., Niederhagen R., Rijneveld J., Schwabe P.: The SPHINCS+ signature framework. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, pp. 2129\u20132146 (2019)."},{"key":"1008_CR10","doi-asserted-by":"crossref","unstructured":"Bitansky N., Haitner I., Komargodski I., Yogev E.: Distributional collision resistance beyond one-way functions. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, pp. 667\u2013695 (2019).","DOI":"10.1007\/978-3-030-17659-4_23"},{"key":"1008_CR11","doi-asserted-by":"crossref","unstructured":"Bitansky N., Kalai Y.T., Paneth O.: Multi-collision resistance: a paradigm for keyless hash functions. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 671\u2013684 (2018).","DOI":"10.1145\/3188745.3188870"},{"key":"1008_CR12","doi-asserted-by":"crossref","unstructured":"Brassard G., H\u00f8yer P., Tapp A.: Quantum cryptanalysis of hash and claw-free functions. In: Latin American Symposium on Theoretical Informatics. Springer, pp. 163\u2013169 (1998).","DOI":"10.1007\/BFb0054319"},{"key":"1008_CR13","doi-asserted-by":"crossref","unstructured":"Buchmann J., Dahmen E., H\u00fclsing A.: XMSS\u2014a practical forward secure signature scheme based on minimal security assumptions. In: PQCrypto 2011: Post-Quantum Cryptography, Vol. 7071 of LNCS. Springer, pp. 117\u2013129(2011).","DOI":"10.1007\/978-3-642-25405-5_8"},{"key":"1008_CR14","doi-asserted-by":"crossref","unstructured":"Chailloux A., Naya-Plasencia M., Schrottenloher A.: An efficient quantum collision search algorithm and implications on symmetric cryptography. In: Advances in Cryptology: ASIACRYPT 2017, Vol. 10625 of LNCS. Springer, Berlin, pp. 211\u2013240 (2017).","DOI":"10.1007\/978-3-319-70697-9_8"},{"key":"1008_CR15","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd I.B.: Collision free hash functions and public key signature schemes. In: Advances in Cryptology: EUROCRYPT\u2019 87, Vol. 304 of LNCS. Springer, Berlin, pp. 203\u2013216 (1988).","DOI":"10.1007\/3-540-39118-5_19"},{"key":"1008_CR16","doi-asserted-by":"crossref","unstructured":"Dubrov B., Ishai Y.: On the randomness complexity of efficient sampling. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC \u201906. Association for Computing Machinery, pp. 711-720 (2006).","DOI":"10.1145\/1132516.1132615"},{"key":"1008_CR17","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF02772959","volume":"51","author":"P Erd\u00f6s","year":"1985","unstructured":"Erd\u00f6s P., Frankl P., F\u00fcredi Z.: Families of finite sets in which no set is covered by the union of r others. Isr. J. Math. 51, 79\u201389 (1985).","journal-title":"Isr. J. Math."},{"key":"1008_CR18","unstructured":"Gennaro R, Trevisan L.: Lower bounds on the efficiency of generic cryptographic constructions. In: 41st Annual Symposium on Foundations of Computer Science, FOCS2000. IEEE, pp. 305\u2013313 (2000)."},{"issue":"1","key":"1008_CR19","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/S0097539704443276","volume":"35","author":"R Gennaro","year":"2005","unstructured":"Gennaro R., Gertner Y., Katz J., Trevisan L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput. 35(1), 217\u2013246 (2005).","journal-title":"SIAM J. Comput."},{"key":"1008_CR20","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 (1996).","DOI":"10.1145\/237814.237866"},{"issue":"1","key":"1008_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/130938438","volume":"44","author":"I Haitner","year":"2015","unstructured":"Haitner I., Hoch J.J., Reingold O., Segev G.: Finding collisions in interactive protocols\u2013tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput. 44(1), 193\u2013242 (2015).","journal-title":"SIAM J. Comput."},{"key":"1008_CR22","first-page":"647","volume":"7073","author":"D Hofheinz","year":"2011","unstructured":"Hofheinz D., Jager T., Kiltz E.: Short signatures from weaker assumptions. Adv. Cryptol 7073, 647\u2013666 (2011).","journal-title":"Adv. Cryptol"},{"key":"1008_CR23","first-page":"179","volume":"10625","author":"A Hosoyamada","year":"2017","unstructured":"Hosoyamada A., Sasaki Y., Xagawa K.: Quantum multicollision-finding algorithm. Adv. Cryptol. 10625, 179\u2013210 (2017).","journal-title":"Adv. Cryptol."},{"key":"1008_CR24","doi-asserted-by":"crossref","unstructured":"H\u00fclsing A., Rausch L., Buchmann J.: Optimal parameters for $$\\rm XMSS ^{MT}$$. In: CD-ARES 2013: Security Engineering and Intelligence Informatics 8128, 194\u2013208 (2013).","DOI":"10.1007\/978-3-642-40588-4_14"},{"key":"1008_CR25","doi-asserted-by":"crossref","unstructured":"H\u00fclsing A., Rijneveld J., Song F.: Mitigating multi-target attacks in hash-based signatures. In: Public-Key Cyptography\u2014PKC 2016.","DOI":"10.1007\/978-3-662-49384-7_15"},{"key":"1008_CR26","unstructured":"Impagliazzo R.: A personal view of average-case complexity. In: Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, IEEE, pp. 134\u2013147 (1995)."},{"key":"1008_CR27","doi-asserted-by":"crossref","unstructured":"Impagliazzo R, Rudich S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 44\u201361 (1989).","DOI":"10.1145\/73007.73012"},{"key":"1008_CR28","doi-asserted-by":"crossref","unstructured":"Komargodski I., Yogev E.: On distributional collision hashing. In: Advances in Cryptology\u2014CRYPTO 2018 10992, 303\u2013327 (2018).","DOI":"10.1007\/978-3-319-96881-0_11"},{"key":"1008_CR29","doi-asserted-by":"crossref","unstructured":"Komargodski I., Naor M., Yogev E.: Collision resistant hashing for paranoids: Dealing with multiple collisions. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, pp. 162\u2013194 (2018).","DOI":"10.1007\/978-3-319-78375-8_6"},{"key":"1008_CR30","unstructured":"Lamport L.: Constructing digital signatures from a one way function. Technical report, Technical Report SRI-CSL-98, SRI International Computer Science Laboratory (1979)."},{"key":"1008_CR31","unstructured":"Leighton F.T., Micali S.: Large provably fast and secure digital signature schemes based on secure hash functions. US Patent 5,432,852.https:\/\/www.google.com\/patents\/US5432852 (1995)."},{"key":"1008_CR32","doi-asserted-by":"crossref","unstructured":"Liu Q., Zhandry M.: On finding quantum multi-collisions. In: Advances in Cryptology\u2014EUROCRYPT 2019 11478, 189\u2013218 (2019).","DOI":"10.1007\/978-3-030-17659-4_7"},{"key":"1008_CR33","doi-asserted-by":"crossref","unstructured":"McGrew D., Curcio M., Fluhrer S.: Leighton-micali hash-based signature. https:\/\/www.rfc-editor.org\/rfc\/rfc8554.html (2019).","DOI":"10.17487\/RFC8554"},{"key":"1008_CR34","doi-asserted-by":"crossref","unstructured":"Merkle R.C.: In: Brassard, G. (ed) Advances in Cryptology\u2014CRYPTO \u201989 435, 218\u2013238 (1989).","DOI":"10.1007\/0-387-34805-0_21"},{"key":"1008_CR35","doi-asserted-by":"crossref","unstructured":"Pieprzyk J., Wang H., Xing C.: Multiple-time signature schemes against adaptive chosen message attacks. In: SAC 2003: Selected Areas in Cryptography 3006, 88\u2013100 (2003).","DOI":"10.1007\/978-3-540-24654-1_7"},{"key":"1008_CR36","doi-asserted-by":"crossref","unstructured":"Reyzin L.., Reyzin N.: Better than biba: Short one-time signatures with fast signing and verifying. In: ACISP 2002: Information Security and Privacy 2384, 144\u2013153 (2002).","DOI":"10.1007\/3-540-45450-0_11"},{"key":"1008_CR37","unstructured":"Shor P.W.: Algorithms for quantum computation: discret logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, Ieee, pp. 124\u2013134 (1994)."},{"key":"1008_CR38","doi-asserted-by":"crossref","unstructured":"Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In: Advances in Cryptology\u2014EUROCRYPT\u201998 1403, 334\u2013345 (1998).","DOI":"10.1007\/BFb0054137"},{"issue":"1","key":"1008_CR39","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1093\/ietfec\/e91-a.1.39","volume":"91","author":"K Suzuki","year":"2008","unstructured":"Suzuki K., Tonien D., Kurosawa K., Toyota K.: Birthday paradox for multi-collisions. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 91(1), 39\u201345 (2008).","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"1008_CR40","doi-asserted-by":"crossref","unstructured":"Yehia M., AlTawy R., Gulliver T.A.: Hash-based signatures revisited. A dynamic FORS with adaptive chosen message security. In: Progress in Cryptology\u2014AFRICACRYPT 2020 12174, 239\u2013257 (2020).","DOI":"10.1007\/978-3-030-51938-4_12"},{"issue":"3","key":"1008_CR41","doi-asserted-by":"publisher","first-page":"473","DOI":"10.3934\/amc.2011.5.473","volume":"5","author":"GM Zaverucha","year":"2011","unstructured":"Zaverucha G.M., Stinson D.R.: Short one-time signatures. Adv. Math. Commun. 5(3), 473 (2011).","journal-title":"Adv. Math. Commun."},{"issue":"7\u20138","key":"1008_CR42","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\u20138), 557\u2013567 (2015).","journal-title":"Quantum Inf. Comput."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01008-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-022-01008-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01008-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,7]],"date-time":"2022-03-07T10:10:10Z","timestamp":1646647810000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-022-01008-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,6]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1008"],"URL":"https:\/\/doi.org\/10.1007\/s10623-022-01008-4","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2022,2,6]]},"assertion":[{"value":"18 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}