Score:0

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

cn flag

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

poncho avatar
my flag
Do you mean $\mathbb{Z}_p^+$ or $\mathbb{Z}_p^*$? Note that $\mathbb{Z}_p^*$ has order $p-1$...
Mark avatar
ng flag
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.
cn flag
I added the details on the security requirement.
Score:1
ru flag

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.

Geoffroy Couteau avatar
cn flag
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)
cn flag
Sorry. yes, being efficiently computable is a trivial property I had in mind, and also pre-image resistance.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.