4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Jul 18 at 1:43
  • $\begingroup$ 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. $\endgroup$
    – Julian
    Jul 18 at 11:23
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Jul 18 at 11:34
  • $\begingroup$ 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. $\endgroup$
    – Julian
    Jul 18 at 15:15
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Jul 18 at 15:32
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Julian
    Jul 21 at 20:35
  • 1
    $\begingroup$ Yes, as long as the p_i are random independent generators whose discrete log in base G is unknown, this generalization works perfectly fine :) $\endgroup$ Jul 21 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.