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.

  • 4
    $\begingroup$ Are you perhaps looking for a solution to Yao's Millionaires' Problem? (Is A > B, without disclosing what A and B are) $\endgroup$
    – Riking
    Commented Jan 6, 2016 at 18:12
  • $\begingroup$ You should look into order revealing encryption. The 2015 result with Wu as an offer is really simple, I implemented it in a matter of hours including integration with a REST API. $\endgroup$ Commented Jan 6, 2016 at 18:48
  • 2
    $\begingroup$ That should have read "with Wu as an author" $\endgroup$ Commented Jan 6, 2016 at 19:01
  • $\begingroup$ Is this the multilinear maps one or the one that just uses PRFs? Would you be willing to send me the source @ThomasM.DuBuisson ? $\endgroup$
    – pg1989
    Commented Jan 6, 2016 at 19:45
  • 3
    $\begingroup$ If you know hash(A), and have the ability to compute hash(x) for any x, what stops you doing a binary search to find A? $\endgroup$ Commented Jan 7, 2016 at 5:20

5 Answers 5


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.

  • 2
    $\begingroup$ I'll select this one as the answer, since I understood this explanation more quickly than the other ones. :) $\endgroup$ Commented Jan 6, 2016 at 15:42
  • $\begingroup$ This does assume a full ordering of the input domain, though. If the number of equivalence classes is no more than the number of possible outputs, then the pigeon hole principle does not hold. But here it's given that A and B are integers, where the number of equivalence classes is (literally!) infinite. $\endgroup$
    – MSalters
    Commented Jan 7, 2016 at 15:26
  • $\begingroup$ I think that prove does not really make sense but it is to long to describe this in a comment so I post an answer crypto.stackexchange.com/a/31765/1915 $\endgroup$
    – miracle173
    Commented Jan 7, 2016 at 23:29

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.

  • $\begingroup$ Well if the range is not smaller than the domain can you really call it a hash-function? The other answers work for general hash-functions not just hash-functions with cryptographic properties. So those are really more general. Of course your point is good as well though. $\endgroup$
    – Guut Boy
    Commented Jan 7, 2016 at 12:21
  • 2
    $\begingroup$ We do not have a precise definition of hash; SHA-512 restricted to 60-byte input could be said to be a hash @Guut Boy $\endgroup$
    – fgrieu
    Commented Jan 7, 2016 at 12:50
  • $\begingroup$ The attacker would need to make one call to the hash function for every bit in the encrypted text - Also the pattern of his tries needs to be fairly specific. So being able to obtain output for arbitrary input is insufficient, if the program that produces this output is under our control we can foil his search by throttling techniques. $\endgroup$
    – Taemyr
    Commented Jan 7, 2016 at 13:54

Property: There is a possibility to decide if $A > B$ from $\text{hash}(A)$ and $\text{hash}(B)$ with $A$ and $B$ being integers

  1. 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.

  2. 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.

  3. 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.

  4. 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$.

  • 2
    $\begingroup$ Your points are technically correct, but since this is crypto.se we do assume that "hash function" has the cryptographic meaning. Questions about non-cryptographic hashes are considered off topic. $\endgroup$
    – otus
    Commented Jan 8, 2016 at 15:29

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.

  • $\begingroup$ That is wrong. The OP does not require that H(A)<H(B) if A<B. $\endgroup$
    – miracle173
    Commented Jan 7, 2016 at 9:41
  • $\begingroup$ If you have hash(A) and hash(B) with A and B being integers, you can tell if A is greater than B, for $a < b$, this means either $H(a) < H(b)$ or $H(a) > H(b)$. I chose the first option. You need only one test to know which option is the one used in $H$, therefore it does not impact on the solution. $\endgroup$
    – Biv
    Commented Jan 7, 2016 at 11:48
  • 3
    $\begingroup$ No, that does not mean that $H(a)<H(b)$ or $H(a)>H(b)$. It means that you have a function $f$ and $f(H(a),H(b))$ returns 'true' if $a<b$ and 'false' if not. Of course this function reduces a total order relation on $\{H(0),...,H(2^{n-1})\}$ but it does definitely not mean that $0≤H(0)<H(1)<…<H(2n−1)<2^n$ $\endgroup$
    – miracle173
    Commented Jan 7, 2016 at 12:41

In general yes, but the hash function will not be cryptographic.

  1. I give you h(X)

  2. select A,B, find h(A),h(B)

  3. compare h(X) > h(A)
  4. compare h(B) > h(X)
  5. therefore h(A) < h(X) < h(B)
  6. make A bigger, B smaller
  7. repeat 2.~6., until A + 2 = B
  8. Now A + 1 = X
  9. You discovered X from h(x)
  10. therefore h() is not preimage resistant
  • 1
    $\begingroup$ This is the same proof as fgrieu. $\endgroup$
    – Biv
    Commented Jan 10, 2016 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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