# Hash function and operation commuting over composition

Is there a hash function $$H$$ and operation $$\otimes$$, which fulfill the following property?

$$H(A) \otimes H(B) = H(A \otimes B)$$

$$A$$ and $$B$$ are two byte blocks of identical length, if necessary restricted to a fixed length (e.g. 128 bytes). $$H$$ should be a cryptographic hash function, in particular, it should be pre-image and collision resistant.

Idea

One idea based on a system of equations using $$XOR$$ I asked in the mathematics forum. But I am mostly interested in existing approaches or a reasoning why this might not be possible.

• Say that $x = H(A) \otimes H(B)$ and $y = A \otimes B$. Then the equation read: let there be a $y$ so that $H(y) = x$. That violates pre-image resistance. That means that $H$ cannot be a regular hash. I'm not sure if I can extend that to collision resistance though. Jul 18 at 1:43
• Thanks for your answer. I don't quite understand how you would obtain a $y$ now from $x$, so that $H(y) = x$. Maybe you could elaborate a little further, I am not a crypto expert. Jul 18 at 11:23
• It's not an answer, it was merely a musing, and since you haven't included pre-image resistance in your question it cannot be one either. I was just hoping to get some greater minds some kind of start. Jul 18 at 11:34
• Yes, thanks. Actually pre-image resistance is a requirement, I updated the question accordingly. I also added a second idea which is better than the first one I hope. Jul 18 at 15:15
• The initial question was small enough to be understood, but adding different methods will quickly make this off topic, as full analysis of designs leads to countless comments and updates of the original question. Jul 18 at 15:32

If you allow different operations $$(\oplus, \otimes)$$ on the input and the output, then there is such a property for the Pedersen hash function. Fix a group $$\mathbb{G}$$ of order $$p$$ with two generators $$(g,h)$$, and assume that computing the discrete logarithm of $$h$$ in base $$g$$ is hard. Then the function $$H: \mathbb{Z}_p \times \mathbb{Z}_p \mapsto \mathbb{G}$$ which maps $$(a,b) \in \mathbb{Z}_p \times \mathbb{Z}_p$$ to $$H(a||b) = g^ah^b$$ is a collision-resistant hash function (under the discrete logarithm assumption) which is compressing by roughly a factor 2 (over groups where group elements can be represented compactly).
Then, defining $$\oplus: ((a,b), (a',b')) \rightarrow (a+a', b+b')$$ and $$\otimes$$ to be the group operation, we have $$H(a,b)\otimes H(a',b') = H((a,b)\oplus (a',b'))$$.
I am not aware of any example where $$\oplus = \otimes$$.
• Yes, $H(A) \otimes H(B) = H(A \oplus B)$ would work for me. Based on your idea, couldn't I split my block into $n$ integers $x_0$, ..., $x_{n-1}$ and define $H$ as $H(x) = \sum_{i=0}^{n-1} x_i \times p_i$, where $p_0$, ..., $p_{n-1}$ are constant points on an elliptic curve $G$? The hash would then be a point on $G$. $\oplus$ would be ordinary integer addition in this case and $\otimes$ would be addition in $G$. That way my compression would be $n$-fold instead of 2, wouldn't it? Jul 21 at 20:35