Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Is it possible to construct a hash function with the following property?
If you have hash(A) and hash(B) with A and B being integers, you can tell if A is greater than B -- without however knowing the actual values of A and B.
Even better: If you have hash(A) and hash(B) with A and B being ordered sets of strings, you can tell which elements of A overlap with B (e.g. those at position 1 and 3 in the ordered set) -- without however knowing the actual contents of A and B.
For hash function $h : \{0,1\}^* \rightarrow \{0,1\}^k$, this is not possible. This is because there are more possible inputs than outputs (pigeon hole principle). And this means that for some $A < B$ we have $h(A) = h(B)$. Thus there will be no way to tell the order of $A$ and $B$.
Addition: To address some of the comments; note that this answer only talks about hash functions defined as functions where the domain is the set of all bit strings and the codomain a set of bit strings of some fixed length $k$. It also assumes that inputs $A$ and $B$ are interpreted as integers (as specified in the question).
The argument only uses that such a hash function must have collisions. We can in fact generalize the argument to any hash function with collisions (i.e., also functions with different domain and codomains). Note that the argument only assumes the existence of collisions and thus holds even if the hash function is collision resistant.
The argument says that for such hash functions there will be some pairs of inputs, those defining a hash function collision, where the order cannot be decided from the hash alone. What happens on other inputs pairs the argument does not directly say anything about.
It is true however, as some comments point out, that if we define hash functions to include functions completely without collisions, then the argument does not hold for all hash functions. However, for functions where my argument does not apply we can use the argument of fgrieu, to show that a hash function with the desired properties can at least not be pre-image resistant.
No, it is not possible to construct a function $\operatorname{Hash}$ with the desired properties, as long as an adversary is able to obtain the output of that function for arbitrary input (even if the function takes an additional secret parameter unknown to an adversary).
Proof sketch: given $A=\operatorname{Hash}(X)$ for unknown integer $X$, we can find $X$ with $O(\log(X))$ evaluations of $\operatorname{Hash}$, using dichotomic search.
Addition: The above argument still works (contrary to that in two other answers) if the function has finite input domain smaller than the output domain (e.g. $\{0,1\}^j\to\{0,1\}^k$ with $j<k$ ), or/and output domain $\{0,1\}^*$. However the arguments in these other answers works even if the adversary has limited access to the hash function.
Property: There is a possibility to decide if $A > B$ from $\text{hash}(A)$ and $\text{hash}(B)$ with $A$ and $B$ being integers
The answer of @fgrieu shows that a cryptographic hash function cannot have this property because it would become insecure. For all hash function including non cryptographic hash functions the answer of @GuutBoy states that a hash function cannot have the property but the arguments don't convince me.
Of course it is right that it is not possible to deduce $A \gt B$ or not if one only knows $h(A)$ which is equal to $h(B)$, but if the range of values for a hash function is large enough the probability that you have to process an $h(A)$ and $h(B)$ with $h(A)=h(B)$ is negligible. So if you have a hash function that allows to decide if $A \gt B$ or not based on $h(A)$ and $h(B)$, if $h(A)\ne h(B)$ then probably you can use such for the procedure you plan (you didn't tell you why do you need such a function) The existence of such a hash function is not disproved by the arguments of @GuutBoy.
There is a special type of hash functions called perfect hash function
A perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions.
So a perfect hash function is injectiv. It seems to be wrong to state that a hash function maps a larger set to a smaller set. The article also defines order preserving and monotone minimal perfect hash functions that have the required property.
If a hash function is injective it is a hash function with this property: for $h(A)$ and $h(B)$ calculate $A$ and $B$ and decide if $A \gt B$. The calculation make take a long time or practically be impossible but $A$ and $B$ is well defined because $h$ is injectiv. But now assume you have a hash function that maps values from a larger set in a smaller set and has a good uniform property. Most of the hash values have mapped one or two values on them. So if you have two hash values $h(A)$ and $h(B)$ there is a high probability that at least for one of them, e.g. $A$, there exist another value $C$ such that $h(A)=h(C)$. An for a lot of such tuples $A$ and $B$ we have $A > B$ and and $B>C$. So you cannot decide from $h(A)$ and $h(B)$ if $A > B$ for a lot of values. For such hash function the property cannot not hold for a lot of tuples $A$ and $B$.
The output size of your hash function is fixed to let's say $n$ bits. The maximum output number you can provide is $2^n - 1$. Should you be able to construct such a function $H$ then for any number under $2^n$, it would preserve the order as demanded. Therefore $H$ is the identity as : $0 \leq H(0) < H(1) < \ldots < H(2^n -1) < 2^n$.
Conclusion, there can't be such a hash function.
In general yes, but the hash function will not be cryptographic.
I give you h(X)
select A,B, find h(A),h(B)
