Is it possible to construct a binary reducing function based on any existing cryptographic hash function satisfying the associative property but not the commutative property? So formally:
Using an existing hashing function $h: \mathbb{B}^* \rightarrow \mathbb{B}^k $ to construct $R: \mathbb{B}^* \times \mathbb{B}^* \rightarrow \mathbb{B}^{k'}$ so that
- $R(R(a,b),c) = R(a,R(b,c))$, for all $a, b, c \in \mathbb{B}^*$ (associativity)
- $R(a,b) \neq R(b,a)$, for some $a, b \in \mathbb{B}^*$ (non-commutativity)
- $R$ is as secure as $h$ in sense of
- pre-image resistance, applied to both arguments, and concatenated
- second pre-image resistance, applied to both arguments, and concatenated
- collision resistance, applied to both arguments, and concatenated
- additionally, it should be as hard to find $a, b \in \mathbb{B}^*, a \neq b$ that $R(a,b) = R(b,a)$ as to find $a, b \in \mathbb{B}^*, a \neq b$ that $h(a)=h(b)$, except the case* where $b = R(a,a)$
where:
- $\mathbb{B} = \{0, 1\}$, a bit
- $k, k' \in \mathbb{Z}^+$, the output length of the hash and reducing functions
also, if needed, more than one base hashing function $h$ could be used.
Background
The purpose of this construction is to allow the calculation of a collective hash value of an ordered list that can be carried out with arbitrary combinations in any order of the reducing function. So the ultimate goal is to construct a function $H: (\mathbb{B}^*)^* \rightarrow \mathbb{B}^k$ that could be calculated by independent multiple steps.
*the reason to make an exception in the last property is that giving the application, it makes perfect sense that $H(\{a,a,a\})$ gives the same result regardless of how you calculate it (credit goes to poncho; refer to his answer).
This question is quite similar to Associative standard cryptographic hash function, but not exactly the same. This answer might be useful: https://crypto.stackexchange.com/a/17936/19959
