Score:4

Hash function and operation commuting over composition

ca flag

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.

Maarten Bodewes avatar
in flag
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.
Julian avatar
ca flag
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.
Maarten Bodewes avatar
in flag
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.
Julian avatar
ca flag
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.
Maarten Bodewes avatar
in flag
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.
Julian avatar
ca flag
Point taken, I hid them as spoilers to avoid distraction. Actually I wouldn't mind some comments on the ideas.
Score:1
cn flag

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

Then

Julian avatar
ca flag
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?
Geoffroy Couteau avatar
cn flag
Yes, as long as the p_i are random independent generators whose discrete log in base G is unknown, this generalization works perfectly fine :)
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.