Hash function

[anas....@gmail.com]

Hi,

   I want to ask if there is any hash function that verify :

          hash(a,b) = hash(b,a)

   I mean  :

      if hash(x,y) = hash(Y,X) ==> X=x and Y=y

   if not, can you give me any other proposition to frame this need.


Thanks,

[Chuck Simmons]

You can certainly construct a hash function where hash(a,b) = hash(b,a).  However, since hash functions map very large input spaces into small output spaces, it is generally not the case that "hash(x) == hash(A) ==> x = A".

If hash(x, y) = hash(Y, X), then it may be the case that x=Y and y=X.

Do you want to provide more context for the discussion?

g'luck, Chuck

--
You received this message because you are subscribed to the Google Groups "Hash Functions" group.
To unsubscribe from this group and stop receiving emails from it, send an email to hash-function...@googlegroups.com.
To post to this group, send email to hash-fu...@googlegroups.com.
Visit this group at http://groups.google.com/group/hash-functions.
For more options, visit https://groups.google.com/d/optout.

[Andres Valloud]

Hello...

> I mean :
>
> if hash(x,y) = hash(Y,X) ==> X=x and Y=y

Are you asking that hash(x,y) provides unique identifiers?

Andres.

[Paul Hsieh]

If you want hash(a,b) = hash(b,a) and easy way to do this is via hash(a,b) = hash1(a) + hash1(b).  You can replace the + with xor, and you can do other things like: hash(a,b) = G(H(hash1(a)) + H(hash1(b))), where G and H are some sort of "inverse permutation functions".  This is equivalent to just hash(a,b) = K(hash1(a)+hash1(b)), since you can hide H inside of hash1.  This is useful if you are trying to avoid hash(a,b) + hash(c,d) = hash(a,c) + hash(b,d) properties.

To also have the property: "if hash(x,y) = hash(Y,X) => X=x and Y=y" is basically a contradiction.  The first condition is specifically to give you the property of swapping x and y.  So by necessity you have: hash(x,y) = hash(a,b) => x=a and y=b, or x=b and y=a.  I assume you want to have this property with this one exception.

A hash function never has the deterministic property of hash(A) = hash(B) <=> A = B.  But secure hash functions like SHA256 or Keccak have the property that there is no single known counter-example of "hash(A) = hash(B) => A = B".  That's good enough for many real-world applications (like git).  So if that's good enough for you, you can choose one of these functions for hash1() and another similar function (simplified for the fixed size of the hash1() output) for K().  Presumably you just want K() to be difficult to invert.  This is not a fast solution, but it should work.

--

Paul

[Andres Valloud]

> A hash function never has the deterministic property of hash(A) = hash(B) <=> A = B.

I wouldn't say "never". I'd say hash functions don't *need* to
satisfy hash(A) = hash(B) <=> A = B, although some might --- e.g.
precalculate unique hash values and store them in the objects hashed,
so the hash function simply returns the precalculated value.

[Anas YOUSFI]

Thanks for you all,

   I know that hash(x) == hash(A) ==> x = A not always true. The aim is to compare two algorithms :  
  

    -  First Algorithm :

      1-         A table contains two informations : hash(a) and hash(b)

      2-         given x and y : ( x always different to y :  x!=y)

      3-           if ( (hash(x) == hash(a) and hash(b) == hash(y))    or  (hash(x) == hash(b) and hash(y) == hash(a)))

      4-                      write : The table contains x and y

   -  Second Algorithm :

      1-       A table contains one information : hash(a,b)

      2-       given x and y : ( the order of x and y is not important, and x!=y)

      3-            if hash(x,y) == hash(a,b)

      4-                      write :  The table contains x and y.

 i want to use the second one, because i'll avoid to store data twice and make just one comparison operation. I know that i can replace the line 3 of the seconde algorithme by :
     hash(x,y) == hash(a,b) or hash(y,x) == hash(a,b)

  For making this operation more quickly, i'm looking if there is any hash function that verify the condition :    hash(x,y) = hash(Y,X) ==> X=x and Y=y  Given that x is always different to y  

  I will testing paul proposition: hash(a,b) = hash(a) XOR hash(b)

--

You received this message because you are subscribed to the Google Groups "Hash Functions" group.
To unsubscribe from this group and stop receiving emails from it, send an email to hash-function...@googlegroups.com.
To post to this group, send email to hash-fu...@googlegroups.com.
Visit this group at http://groups.google.com/group/hash-functions.
For more options, visit https://groups.google.com/d/optout.

--

Anas YOUSFI
Ingénieur ENSIMAG-FRANCE 2012
Ingénieur ENSIAS-MAROC 2011

Mobile France : (+33)0650035181
Mobile Maroc : (+212)673992786

[Andres Valloud]

I don't think those algorithms give correct answers because you could have

hash(a) = hash(c)
hash(b) = hash(d)
a != c, b != d
hash(x) = hash(a)
hash(y) = hash(b)

and the conclusion would be the tables have x and y, which is false.

Where does your problem come from?

Andres.

On 3/31/14 1:21 , Anas YOUSFI wrote:
> Thanks for you all,
>
> I know that hash(x) == hash(A) ==> x = A not always true. The aim is
> to compare two algorithms :
>

> *- _First Algorithm :_*

> 1- A table contains two informations : hash(a) and hash(b)
> 2- given x and y : ( x always different to y : x!=y)

> 3- if ( (hash(x) == hash(a) *and* hash(b) == hash(y))
> *or (*hash(x) == hash(b) *and* hash(y) == hash(a)))

> 4- write : The table contains x and y

> * - _Second Algorithm :_*

> 1- A table contains one information : hash(a,b)
> 2- given x and y : ( the order of x and y is not important,
> and x!=y)
> 3- if hash(x,y) == hash(a,b)
> 4- write : The table contains x and y.
>
> i want to use the second one, because i'll avoid to store data twice
> and make just one comparison operation. I know that i can replace the
> line 3 of the seconde algorithme by :

> *hash(x,y) == hash(a,b) or hash(y,x) == hash(a,b)*

> For making this operation more quickly, i'm looking if there is any
> hash function that verify the condition : hash(x,y) = hash(Y,X) ==>

> X=x and Y=y Given that *x is always different to y
>
> *
> I will testing paul proposition: hash(a,b) = hash(a) XOR hash(b)*
> *

>
>
> 2014-03-31 8:00 GMT+01:00 Paul Hsieh <webs...@gmail.com

> <mailto:webs...@gmail.com>>:

> <mailto:hash-function...@googlegroups.com>.

> To post to this group, send email to hash-fu...@googlegroups.com

> <mailto:hash-fu...@googlegroups.com>.

> Visit this group at http://groups.google.com/group/hash-functions.
> For more options, visit https://groups.google.com/d/optout.
>
>
>
>
> --
> Anas YOUSFI
> Ingénieur ENSIMAG-FRANCE 2012
> Ingénieur ENSIAS-MAROC 2011
> Mobile France : (+33)0650035181
> Mobile Maroc : (+212)673992786
>

> --
> You received this message because you are subscribed to the Google
> Groups "Hash Functions" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to hash-function...@googlegroups.com

> <mailto:hash-function...@googlegroups.com>.

> To post to this group, send email to hash-fu...@googlegroups.com

> <mailto:hash-fu...@googlegroups.com>.