multihash security proofs

[burdges]

Are there any security proofs for multihash or similar constructs? I'd think the results would say roughly that, for some desirable hash function properties, multihash is not-too-unlike a hash function satisfying the weakest version of that property among satisfied by any of the hash functions with which it can be instantiated.

As stated this is false of course, there are countless protocols for which substituting multihash as if it were as hash function will break the protocol, like anything that requires uniqueness, but probably far more. It's worth writing down a general setting in which multihash is not inherently broken though, maybe including signature scheme requirements.

[Stebalien]

As you noted, in general, multihash will have the intersection of the security properties of the set of hash functions you choose. This obviously won't apply to things like "indistinguishable from random data" as the prefix of a multihash isn't random but you'd have to prove things like this on a property-by-property basis.

Using multihash shouldn't affect any "uniqueness" requirements (as long as you constrain the set of hash functions to "safe" hash functions).

[burdges]

It'd completely break VRFs obviously. It slightly weakens anything using Fiat–Shamir, including signature schemes, but you'd never use it for a signature scheme though I guess.

I suppose the real answer might be just to write down the properties one wants when using a hash function as an identifier. It'll be fine for those uses of course.

[Stebalien]

I suppose the real answer might be just to write down the properties one wants when using a hash function as an identifier. It'll be fine for those uses of course.

Yeah, that would be nice. Really, it turns out that those properties aren't the same as those provided by a cryptographic hash function. For example, the identity function is a perfect identifier.