I’m somewhat confused by the example at the end. SHA-3 (and other hash functions) are not injective, so it’s not at all clear what “the preimage” means here. The example appears to choose a preimage of length 512 bits (matching the output), but SHA-3 is not designed to be injective on that domain either. It almost certainly is not, and therefore also not surjective so that some bitstrings have no such preimage.
It would be possible to restrict the chosen preimages further, e.g. to the lexicographically first preimage, but then just knowing that SHA3(x) = y does not guarantee that x is the preimage as defined.
Maybe a function that is guaranteed to be bijective yet difficult to invert would work better here?
I’m somewhat confused by the example at the end. SHA-3 (and other hash functions) are not injective, so it’s not at all clear what “the preimage” means here. The example appears to choose a preimage of length 512 bits (matching the output), but SHA-3 is not designed to be injective on that domain either. It almost certainly is not, and therefore also not surjective so that some bitstrings have no such preimage.
It would be possible to restrict the chosen preimages further, e.g. to the lexicographically first preimage, but then just knowing that SHA3(x) = y does not guarantee that x is the preimage as defined.
Maybe a function that is guaranteed to be bijective yet difficult to invert would work better here?
Hmm true. A random permutation oracle I guess? Or “random preimage” of SHA-3?