Hi,

I need to know if there is some kind of a homomorphic hash function,
and how it is weaker than normal hash functions (if it exists).

I am looking for a specific construction of one, that is implementable in
practice.

Thanks,
Petar

---

Request for Question Clarification by rbnn-ga on 06 Nov 2002 18:14 PST

In what context did you see this reference?

---

Clarification of Question by petar-ga on 06 Nov 2002 22:49 PST

This is in a specific context that I have created through my research.
I have n messages, and each of them has a publicly known hash value.
Let's say you have messages x1,x2 and x3. Ands it is a oublic knoledge
what h(x1),h(x2) and h(x3) are. In the context my algorithm, people
receive
x1*x2, for example, and they need to verify that h(x1*x2) checks.
They only know h(x1) and h(x2), so its got to be the case that
h(x1*h2)=h(x1)*h(x2), so they can check it.

Hi, petar-ga:

If the question is, have I ever heard of such a description, the
answer is no.

Of course if you have a ring structure and a homomorphism defined on
it, then you could use that homomorphism as a hash function (presuming
that the range is finitely representable).  To give a simple example,
you might "hash" members of a class of real-valued functions by
storing their values at three chosen values of the domain, as a triple
of real numbers.

I've never seen an application that would make use of such a
"structure preserving" property of the hash function; it would be
interesting to learn more about what advantage this provides.

regards, mathtalk-ga

Well, yeah, but the whole difficulty is in finding a complelling
proof that the created function IS one-way under some interpretation.

I still can't believe that homomorphic hash functions haven't been 
mentioned in literature. Strange.

Petar

In fact, what you are suggesting is very easily invertible, i.e. you 
can easily find a pre-image of anything. Which is exactly what you want
not to be the case for hash functions.

Petar

I get the feeling that what you are calling a hash function is what I
would call a trapdoor or "one-way" function.

To me a hash function is a many-to-one function, useful in the
compression of sparse storage schemes, and hence in related algorithms
like sorting and searching.

I don't know what your application is, but the RSA encryption scheme
is essentially a group homomorphism on the abelian multiplicative
group of Z/mZ*, residues of Z/mZ which are coprime to m with m = pq a
difficult to factor product of two distinct primes.

Is something of that nature of interest to you?

regards, mathtalk-ga

Well, that is one possibility, except for an open question stays:
How do you apply it on big messages. The RSA thing is has the
same domain and range. A hash function has a much smaller range.

You can come up with ways to apply the RSA idea on long messages
but than you have to prove that one wayness is preserved, which
will take a while to prove probably.

I was hoping that somebody had done it already and that there was a reference
to the result.

Petar

I do not understand the question.

I'm not sure what the phrase "homomorphic hash function" means. I have
not seen the word "homomorphic" before, and "hash function" can have
many different meanings.

A "homomorphism" itself is a word, but it's a word with many different
meanings. Typically a homomorphism of algebraic structures is a
structure-preserving map of such structures.

The question also uses the symbol "*" but I don't know what this means
in this context.

Anyway, I have been thinking about the question and I did read the
comments so far, but I am unable to progress with unambiguous
definitions of the terms:
  homomorphic
  hash function
  "*"

Since this is a coding question, I think there are a few things we can
assume about the function that Petar wants.

1: h(x) is a function of (large) natural numbers. x is a message to be
enciphered, and we can always describe x as a string of integer values
in some predictable way (e.g., binary ascii).

2: By "homomorphic" he means that given two inputs, x_1 and x_2, then
the h(x_1*x_2)=h(x_1)*h(x_2), for some operation *. From the above
assumption and the context, I'm guessing that * is multiplication, but
I can't be sure.

3: I am not sure exactly what is necessary for a hash function in this
case. Does it just need to be many-to-one? Does it need to be mixing
or have any other special properties like that?

I can come up with a simple example of a many-to-one function of the
natural numbers that displays the property described in 2 above, but
it's pretty useless and probably not what Petar has in mind. If Petar
or anyone else would like to hear it, I'll post it.

By a hash function I mean a function that takes as input some message.
It can be arbitrarily big, e.g. it can be a text or a binary file. The
output of this function is a fixed bitlength number, e.g. 160-bit number.
The function must be one-way, meaning that for any given 160-bit number
it must be hard to find a message that would hash to this number.
Finally, by homomorphic, I mean the following.
When the messages and the hashes (the outputs of the function) are interpreted
as elements of some groups (which you are free to choose). it needs to be the
case that the hash function preserves the group operation. Furthermore,
both groups must be abelian and both group operations must be easily invertible.

Petar

So are you saying that your group needs to have two invertible
operations (i.e., it's a field)?

Here's the example I was thinking of before. I think it fulfills your
technical requirements but I doubt it's what you want. Also I am going
to consider only one group operation. Let me know if it's at least
along the lines you are thinking of.

Let P be some sufficiently large prime bigger than the largest message
you are likely to transmit. Let N be the set of natural numbers. The
group we will consider is N mod P with the operation * (i.e., standard
multiplication of natural numbers, mod P).

Define h(x)=0 if x is even, and h(x)=1 if x is odd.

If x_1 or x_2 is even (or if both are even) then x_1*x_2 is even and
h(x_1*x_2)=0, likewise one of h(x_1) and h(x_2) is zero, so
h(x_1)*h(x_2) is 0.
If x_1 and x_2 are both odd, then x_1*x_2 is odd and h(x_1*x_2)=1.
Likewise h(x_1)=1 and h(x_2)=1, so h(x_1)*h(x_2)=1

So the output of h is a fixed-bitlength number (in this case 1 bit)
and is acting on an abelian group. If you use + as your operation,
h(x) is not quite homomorphic anymore, since if x_1 and x_2 are both
odd, then h(x_1+x_2)=0 but h(x_1)+h(x_2)=2. But I am not sure if you
need the function to be homomorphic for both group operations (I
didn't quite understand your wording).

This function has the advantage that it's easy to do (just look at the
last bit of x_1, x_2, and x_1*x_2) but the disadvantage that it's
lame. But someone could probably come up with something similar. In
fact, it strikes me that modulo as a function (for some prime Q)
behaves pretty much the same way, with more outputs.

Am I thinking along the right lines here or am I totally off base?

Sorry, you misunderstood me. The space of messages is one group, the
space of outputs (i.e. hashes) is another group. Each group is abelian
and has *one* operation. This operation has to
be invertible.

The trickiest property that the hash function needs to abide by is
that it must be hard to invert.
Your example is trivial to invert.

Hope this helps.

Petar

Other than being obvious to invert (where by inverting here I suppose
you mean being able to determine the preimage set of any particular
output of h(x)) does my silly function (under * ) otherwise meet the
criteria that you need for your hash function? I'd like to know so
that I am sure I'm understanding your requirement of "homeomorphic".

Oops. Homomorphic. Not homeomorphic. Sorry.

You seem to be a bit confused as follows. Your program meets the
homomorphism requirement.
However, when I said that the "group operation needs to be invertible"
I didn't mean that
the function h(x) needs to be invertible. These two have nothing to do
with each other.
H(x) should not be invertible. For a function not to be invertible
means that given a possible
output, you cannot find the set of inputs that produce it. On the
other hand, for a group operation
to be invertible means that for each element g in the group there is
an element k, such that
g*k = 1.

Petar

Oops, that's my fault. What was I thinking?

I noticed your requirement that the group be abelian in your original
description, and then proceeded to file that information away (read:
forget) as soon as I decided on using natural numbers modulo P (where
multiplication is definitely commutative).

Now that I am not confusing myself any more on the issue, I'll see
what I can come up with.