Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I am looking for a standard hash function which satisfies the following property:
A hash function $H(a,b) = F(h(a),h(b))$ with $h$ (within $F$) any standard cryptographic hash function and $F$ an associative function.
Is there any standard hash function(e.g. RIPEMD-160, SHA1) for which I can easily implement the associative function (like xor-ing or something similar)?
One of the simplest associative functions that isn't commutative is concatenation:
$$H(a,b) = h(a) || h(b)$$
Yes, it doubles the output length, but it is as strong as $h$ against collisions. I offer this partly as a serious suggestion (it's simple) and partly to illustrate that your requirements are quite broad.
If you don't need $H$ to be collision-resistant, you can use
$$H(a,b) = h(a) \times h(b) \bmod p$$
where $p$ is a large prime such that $p-1$ has a large divisor (and in particular, the discrete log problem modulo $p$ is hard), and with $h:\{0,1\}^* \to \mathbb{Z}/p\mathbb{Z}$ a hash function that outputs numbers in the range $[0,p-1]$.
If $h$ is a cryptographic-strength hash function, this will be one-way (preimage-resistant) in the random oracle model. As poncho explains, it won't be collision-resistant, because $H(a,b)=H(b,a)$.
You could also consider
$$H(a,b) = h_0(a) \times h_1(b) \bmod p$$
where $h_0,h_1$ are two separate cryptographic hash functions (e.g., $h_b(x) = h(b,x)$). This will be one-way and collision-resistant. I don't know whether it will meet your needs, though, because it's not exactly of the form you mention.
See also MuHash, as described here: Does collision resistance stay when extending a hash function to a set domain?
You might also consider a generalization of this that provides associativity but not commutativity. Let $\mathbb{G}$ be any non-commutative group. Then one candidate construction is
$$H(a,b) = h(a) \times h(b) \bmod p$$
where $h:\{0,1\}^* \to \mathbb{G}$ a hash function that outputs group elements.
This gives a candidate construction for each non-commutative group. Will it be secure? I don't know, but I expect that will depend upon $\mathbb{G}$. It seems plausible that with a suitable choice of $\mathbb{G}$, you might be able to design a hash function $H$ that is secure, i.e., one-way and collision-resistant (at least when we model $h$ as a random oracle).
I haven't tried to come up with a specific candidate, but one plausible choice might be letting $\mathbb{G}$ be a suitable set of $2 \times 2$ matrices over a some finite field $\mathbb{F}$, so that $\mathbb{G} = SL_2(\mathbb{F})$. See, e.g., hashing with SL2: Non-commutitive and nonassociative algebraic structures in cryptography for a related scheme. I haven't worked out all the details, but this might give you enough ideas to come up with a candidate scheme that meets all of your requirements.
In general, any type of algebraic identity on $H(a,b)$ in terms of $H(a)$ and $H(b)$ opens up a number of potential attack vectors such as meeting in the middle that make the hash not cryptographically secure. You can look at why we are using triple DES instead of double DES. Therefore, standard cryptographic hash functions are unlikely to have such a property.
If you need hash functions in a not security sensitive way, there are possibilities, like Algebraic Signatures (which you can find with Google Scholar).
