1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$) $\endgroup$ – poncho Dec 30 '14 at 23:25
4
$\begingroup$

I don't believe that any such function can meet the requirements of associativity, pre-image resistance and the 'hard to find commuting operands' simultaneously.

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.

$\endgroup$
  • $\begingroup$ Yep, you're right. Thank you for pointing it out. I'll describe the use case and revise the question tomorrow. It's already too late in my place. $\endgroup$ – Haochen Xie Dec 23 '14 at 17:09

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.