1
$\begingroup$

Is there a hash function that satisfies all the following properties: 1. It is 1 to 1 (no collisions). 2. It can take any size input. 3. For any input, and some desired set of characters, there exists a third set characters that can be appended to the input so that the output starts with the desired characters. 4. All of the other usual requirements of a hash, like computationally infeasible de-hashing? This is a question that popped up from a CS problem I was thinking about, but this part seems more like math, so I asked it here as opposed to on Overflow.

$\endgroup$
  • 1
    $\begingroup$ This is impossible. If the function is 1-1 for input strings of arbitrary length, it cannot have limited output length. Isn't that usually a requirement for hash functions? $\endgroup$ – Hans Engler Mar 6 '18 at 16:12
1
$\begingroup$

The hash functions I am familiar with return a fixed length hash, so cannot be one to one for arbitrary length input. One approach to meet your one to one and arbitrary length input would be to break the input into blocks of fixed length and hash each block. It is not hard to imagine a bijection on the bit strings of a fixed length that is computationally impractical to invert. You can use any block encryption algorithm if you can code it and forget the key. To be able to append text to get the possibility of a desired start to the output, just provide the output blocks in reverse order. As we have a bijection, there is some input block that creates any desired output block, though we don't know how to find it.

$\endgroup$
  • $\begingroup$ If you allow the output to be any size, wouldn't reversing it be harder, as you might not know the input size? $\endgroup$ – William Grannis Mar 6 '18 at 18:35
  • $\begingroup$ @WilliamGrannis I was assuming it can be any size but you know how bigot is at the start. $\endgroup$ – Ross Millikan Mar 6 '18 at 19:46
  • $\begingroup$ Firstly, I assume by "bigot" you mean "big it." Secondly, I mean that Eve, not knowing the size of the message sent from Alice to Bob. If both the output and its size are psuedo-random, then isn't finding the input extra difficult? $\endgroup$ – William Grannis Mar 6 '18 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.