Is there a construction of an order preserving hash function that keeps the preimage property of a crypto hash function? By order preserving hash function (OPHF) i mean for $x<y$ then $OPHF(x) < OPHF(y)$
The problem with a hash function like you ask for is that, if you hash an $n$-bit string and give the hash to someone else, they can recover the string using $n$ hash calculations with a binary search.
For a simple example, let's say the $n=8$, your string is $01011001$ in binary, and its hash is $Y = H(01011001)$.
This flaw is inherent in the idea of order-preserving hashing: if I can obtain the hash of any valid string, then I can always carry out such a search. In fact, even if I can't get the actual hashes, but can only ask you for the result of the comparison between $H(s)$ and $Y$ for some input string $s$, I can still recover your original string without even seeing its hash value!
Basically, if you ever played the "guess what number I'm thinking of?" game as a child, this is exactly the same situation. You have a secret string, and I get to guess a string and see if it's less than or greater than your secret. As in the game, with the right guessing strategy I won't need too many guesses to find the right answer.
|show 10 more comments|