Secure order preserving hash function 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&lt;y$ then $OPHF(x) &lt; 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)$.


To recover the string from the hash, I start by calculating $X_1 = H(10000000)$ and comparing it with $Y$.  Since $10000000 &gt; 01011001$, and since $H$ is order-preserving, $X_1 &gt; Y$ and I therefore now know that the first bit of your string is $0$.
Next, I'll calculate $X_2 = H(01000000)$ and again compare it with $Y$.  Since $01000000 &lt; 01011001$, this time $X_2 &lt; Y$, and thus I now know that the first two bits of your string are $01$.
Using this knowledge, the next hash I'll calculate will be $X_3 = H(01100000)$.  Since $01100000 &gt; 01011001$, now $X_3 &gt; Y$, and thus I know that the first three bits of your string are $010$.
The next hash I'll calculate will be $X_4 = H(01010000)$, which I'll compare with $Y$ to find the fourth bit of your string, and so on, until I've recovered every bit of your string.


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.