# Associative but NOT Commutative Reducing Function Construction with Existing Hash Function(s)

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

• Actually, associativity implies more commuting pairs than that; if we designate $a^k = H(\{a,a,a,...,a\})$, then $a^i$, $a^j$ are a commuting pair (for any $a, i, j$) – poncho Dec 30 '14 at 23:25

Here's why: suppose we have a preimage $a$; we first check if $H(a,a)=a$. If it is, we found a preimage.
If $H(a,a) = b \ne a$, then we have $H(a,b) = H(a,H(a,a)) = H(H(a,a),a) = H(b,a)$ (because of associativity), and hence we found a commuting pair.