@prefix ns1: . @prefix ns2: . @prefix rdf: . @prefix rdfs: . @prefix xml: . @prefix xsd: . a ns1:Chapter ; ns1:about , ; ns1:author ( ) ; ns1:datePublished "2018-03-31" ; ns1:datePublishedReg "2018-03-31" ; ns1:description """A collision resistant hash (CRH) function is one that compresses its input, yet it is hard to find a collision, i.e. a x1≠x2\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$x_1 \\ne x_2$$\\end{document} s.t. h(x1)=h(x2)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$h(x_1) = h(x_2)$$\\end{document}. Collision resistant hash functions are one of the more useful cryptographic primitives both in theory and in practice and two prominent applications are in signature schemes and succinct zero-knowledge arguments.In this work we consider a relaxation of the above requirement that we call Multi-CRH: a function where it is hard to find x1,x2,…,xk\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$x_1, x_2, \\ldots , x_k$$\\end{document} which are all distinct, yet h(x1)=h(x2)=⋯=h(xk)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$h(x_1) = h(x_2) = \\cdots = h(x_k)$$\\end{document}. We show that for some of the major applications of CRH functions it is possible to replace them by the weaker notion of a Multi-CRH, albeit at the price of adding interaction: we show a constant-round statistically-hiding commitment scheme with succinct interaction (committing to poly(n)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$\\mathsf {poly}(n)$$\\end{document} bits requires exchanging O~(n)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$\\tilde{O}(n)$$\\end{document} bits) that can be opened locally (without revealing the full string). This in turn can be used to provide succinct arguments for any NP\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$${\\textsf {NP}}$$\\end{document} statement.We formulate four possible worlds of hashing-related assumptions (in the spirit of Impagliazzo’s worlds). They are (1) Nocrypt, where no one-way functions exist, (2) Unihash, where one-way functions exist, and hence also UOWHFs and signature schemes, but no Multi-CRH functions exist, (3) Minihash, where Multi-CRH functions exist but no CRH functions exist, and (4) Hashomania, where CRH functions exist. We show that these four worlds are distinct in a black-box model: we show a separation of CRH from Multi-CRH and a separation of Multi-CRH from one-way functions.""" ; ns1:editor ( [ a ns1:Person ; ns1:familyName "Nielsen" ; ns1:givenName "Jesper Buus" ] [ a ns1:Person ; ns1:familyName "Rijmen" ; ns1:givenName "Vincent" ] ) ; ns1:genre "chapter" ; ns1:inLanguage "en" ; ns1:isAccessibleForFree false ; ns1:isPartOf [ a ns1:Book ; ns1:isbn "978-3-319-78374-1", "978-3-319-78375-8" ; ns1:name "Advances in Cryptology – EUROCRYPT 2018" ] ; ns1:keywords "CRH", "CRH functions", "Collision Resistant", "Resistant", "above requirements", "applications", "argument", "assumption", "black-box models", "collision-resistant hash functions", "collisions", "commitment scheme", "cryptographic primitives", "function", "hash function", "input", "interaction", "major applications", "model", "multiple collisions", "notion", "one", "one-way functions", "paranoid", "possible worlds", "practice", "prices", "primitives", "prominent applications", "relaxation", "requirements", "scheme", "separation", "signature scheme", "statements", "succinct arguments", "theory", "turn", "useful cryptographic primitive", "weaker notion", "work", "world", "zero-knowledge arguments" ; ns1:name "Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions" ; ns1:pagination "162-194" ; ns1:productId [ a ns1:PropertyValue ; ns1:name "doi" ; ns1:value "10.1007/978-3-319-78375-8_6" ], [ a ns1:PropertyValue ; ns1:name "dimensions_id" ; ns1:value "pub.1101874799" ] ; ns1:publisher [ a ns1:Organisation ; ns1:name "Springer Nature" ] ; ns1:sameAs , ; ns1:sdDatePublished "2022-05-20T07:47" ; ns1:sdLicense "https://scigraph.springernature.com/explorer/license/" ; ns1:sdPublisher [ a ns1:Organization ; ns1:name "Springer Nature - SN SciGraph project" ] ; ns1:url "https://doi.org/10.1007/978-3-319-78375-8_6" ; ns2:license ; ns2:sdDataset "chapters" . a ns1:DefinedTerm ; ns1:inDefinedTermSet ; ns1:name "Information and Computing Sciences" . a ns1:DefinedTerm ; ns1:inDefinedTermSet ; ns1:name "Data Format" . a ns1:Person ; ns1:affiliation ; ns1:familyName "Komargodski" ; ns1:givenName "Ilan" ; ns1:sameAs . a ns1:Person ; ns1:affiliation ; ns1:familyName "Yogev" ; ns1:givenName "Eylon" ; ns1:sameAs . a ns1:Person ; ns1:affiliation ; ns1:familyName "Naor" ; ns1:givenName "Moni" ; ns1:sameAs . a ns1:Organization ; ns1:alternateName "Cornell Tech, 10044, NewYork, NY, USA" ; ns1:name "Cornell Tech, 10044, NewYork, NY, USA" . a ns1:Organization ; ns1:alternateName "Weizmann Institute of Science, 76100, Rehovot, Israel" ; ns1:name "Weizmann Institute of Science, 76100, Rehovot, Israel" .