# Homomorphic hash from prime order group $G$ to $Z_p$

Let $$G$$ be a cyclic group with the generator $$g$$ and of prime order $$p$$ such that the discrete-logarithm problem is hard in $$G$$.

A hash function is homomorphic if $$H(a\ast b)=H(a)\cdot H(b)$$ (where the operations $$\ast$$ and $$\cdot$$ depend on the groups). Here we do not expect the hash function to be compressing, but collision-resistance (CR) and efficiently computeable.

Now the question is, if there exist such homomorphic hash function from group $$G$$ to $$Z^+_p$$?

• Do you mean $\mathbb{Z}_p^+$ or $\mathbb{Z}_p^*$? Note that $\mathbb{Z}_p^*$ has order $p-1$... Sep 10, 2021 at 15:47
• What do you mean by a "hash"? You haven't stated any target security properties, and $H$ does not seem to have to be compressing.
– Mark
Sep 10, 2021 at 16:44
• I added the details on the security requirement. Sep 13, 2021 at 12:49

Yes. The function is usually referred to as the discrete logarithm function. It is defined by $$H:G\to(\mathbb Z/p\mathbb Z)^+$$ $$H(g^X)=X$$
The function always exists, but if $$G$$ is a cryptographic group, then $$H$$ should be infeasible to compute. Technically, there is one such function for every $$g$$, but they are all multiples of each other.
We would typically just call this a function rather than a hash function. It's certainly not a cryptographic hash function as it can be inverted with $$O(\log p)$$ operations in $$G$$.
ETA: Note that by the homomorphic property $$H(h^a)=aH(h)$$ and so the value of $$H(g)$$ completely determines the function. In other words the discrete logarithm function and its multiples represent all possible homomorphic functions from $$G$$ to $$(\mathbb Z/p\mathbb Z)^+$$. There are no others.
• The function is injective, hence it is in particular (perfectly) collision-resistant (in the sense that collisions do not even exist). Therefore, I guess you should perhaps rethink a bit what you are looking for exactly. In particular, you might also want $H$ to be efficient (here, evaluating $H$ requires computing a discrete logarithm, for which we don't have a general polytime algorithm) Sep 13, 2021 at 13:42