Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
4  
Are you perhaps looking for a solution to Yao's Millionaires' Problem? (Is A > B, without disclosing what A and B are) – Riking Jan 6 at 18:12
    
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. – Thomas M. DuBuisson Jan 6 at 18:48
2  
That should have read "with Wu as an author" – Thomas M. DuBuisson Jan 6 at 19:01
    
Is this the multilinear maps one or the one that just uses PRFs? Would you be willing to send me the source @ThomasM.DuBuisson ? – pg1989 Jan 6 at 19:45
3  
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? – immibis Jan 7 at 5:20
up vote 30 down vote accepted

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.

share|improve this answer
2  
I'll select this one as the answer, since I understood this explanation more quickly than the other ones. :) – RudolfKaiser Jan 6 at 15:42
    
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. – MSalters Jan 7 at 15:26
    
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 – miracle173 Jan 7 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.

share|improve this answer
    
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. – Guut Boy Jan 7 at 12:21
2  
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 – fgrieu Jan 7 at 12:50
    
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. – Taemyr Jan 7 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$.

share|improve this answer
2  
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. – otus Jan 8 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.

share|improve this answer
    
That is wrong. The OP does not require that H(A)<H(B) if A<B. – miracle173 Jan 7 at 9:41
    
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. – Biv Jan 7 at 11:48
3  
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$ – miracle173 Jan 7 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
share|improve this answer
1  
This is the same proof as fgrieu. – Biv Jan 10 at 12:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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