0
$\begingroup$

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$?

$\endgroup$
3
  • 1
    $\begingroup$ Do you mean $\mathbb{Z}_p^+$ or $\mathbb{Z}_p^*$? Note that $\mathbb{Z}_p^*$ has order $p-1$... $\endgroup$
    – poncho
    Sep 10, 2021 at 15:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark
    Sep 10, 2021 at 16:44
  • $\begingroup$ I added the details on the security requirement. $\endgroup$
    – A.Solei
    Sep 13, 2021 at 12:49

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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) $\endgroup$ Sep 13, 2021 at 13:42
  • $\begingroup$ Sorry. yes, being efficiently computable is a trivial property I had in mind, and also pre-image resistance. $\endgroup$
    – A.Solei
    Sep 14, 2021 at 9:51

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.