# Exponentiation for hash function & associativity

Some cryptographic papers use $H^n(x)$ to mean $H(H^{n-1}(x))$ where $H^0(x) = x$ and $H$ is a cryptographic hash. So $H^3(x)$ would be $H(H(H(x)))$.

Is this definition formally correct? It seems to me that cryptographic hash functions are not associative. Does at least power-associativity hold for hash functions?

If it formally shouldn't be written like this, what would be a mathematically correct & short way of describing this kind of functionality?

For a Q/A about what $H^n(x)$ means please see the Q/A on crypto here.

• Hash functions are unary. Associativity is a property of binary operations. – cpast Apr 6 '15 at 16:31
• @cpast You are right of course, but in that case how is exponentiation of unary operations defined? Is it defined at all or is this the same thing as writing $E^2PROM$ instead of just EEPROM? – Maarten Bodewes Apr 6 '15 at 16:41

We have an associative operation here – it is the function composition $\circ$.

For any functions $f : X \to Y$ and $g : Y \to Z$ we have $g \circ f : X \to Z$, defined by $(g \circ f)(x) := g(f(x))$ for all $x \in X$. I heard some authors defined it the other way around, $(f \circ g)(x) := g(f(x))$. I think my version is more common.) This operation is obviously associative, where defined: $$((f \circ g) \circ h)(u) = (f \circ g)(h(u)) = f(g(h(u))) = f((g \circ h)(u)) = (f \circ (g \circ h))(u),$$ thus $(f \circ g) \circ h = f \circ (g \circ h)$.

For functions from one set to itself (i.e. $f : X \to X$) we can compose $f$ with itself, and have then $f \circ f$, $f \circ f \circ f$ and so on, and it is natural to name them $f^2$, $f^3$, etc. This naturally extends to $f^1 = f$ and $f^0 = \operatorname{id}_X$, with $\operatorname{id}_X : X \to X$ being the identity function of $X$ ($\operatorname{id}_X(x) = x$ for all $x \in X$).

When $f$ is bijective, we also naturally have $f^{-1}$, and generally $f^{-n}$, and all the usual properties of powers work: $f^n \circ f^{m} = f^{n+m}$, for example. The power laws actually don't need inverses for non-negative exponents.

The set of all bijective functions from a Set to itself forms a (non-commutative) group with this operations. These groups, as well as many of their subgroups (groups of bijections, which also retain some structural properties = isomorphism groups) are important objects of study.

But your hash functions are usually not bijective, thus they have no inverses, so we get no group. Still the set of functions $h : \{0,1\}^* \to \{0,1\}^*$ is a monoid under composition (associative with a neutral element – the identity function).

Looking just at "hash functions" with a given output size $n$, the set of functions $h : \{0,1\}^* \to \{0,1\}^n \subset \{0,1\}^*$ (which can be seen as a subset of the previous set) still works with the composition, though here there is no working neutral element – so we just have a semigroup.

## For confusion

Sometimes we use the notation $f^n$ for a different function, namely the function defined by $(f^n)(x) := (f(x))^n$. This obviously only makes sense for $f : X \to Y$, when there is an obvious exponentiation operation in $Y$.

This exponentiation is then related to the "point-wise multiplication" operation $f · g : X \to Y$, defined by $(f ·g)(x) = f(x) · g(x)$, which is associative whenever multiplication in $Y$ is associative, and has the constant $\operatorname{const}_{1_Y}$-function as an identity (assuming $1_Y$ is a neutral element in $(Y, ·)$.

This often occurs when talking about real functions, like $\sin^2 + \cos^2 = 1$ meaning $(\sin(\alpha))^2 + (\cos(\alpha))^2 = 1$ (Pythagoras' theorem applied to the unit circle), not $\sin(\sin(\alpha)) + \cos(\cos(\alpha)) = 1$.

It is usually clear from context which meaning of $\square^n$ is meant – in the case of hash functions, we have no obvious multiplication of bitstrings, so the second meaning can't be the right one.

• Good, so we conclude that $f^n(x)$ is perfectly fine for hash functions, even if the set of functions is a semigroup under $o$ instead of a group because the associativity holds for the function under $o$ instead of the single argument? – Maarten Bodewes Apr 6 '15 at 17:16
• +1 From me. We can furthermore say that $\left <H, \circ\right >$ is an abelian monoid which is isomorphic (as a monoid) to $\left <\mathbb{N},+\right >$ (assuming that your definition of $\mathbb{N}$ includes $0$). – rnrstopstraffic Apr 6 '15 at 17:19
• @MaartenBodewes the associativity holds for the operation of composition (which can be considered a binary function $g(f,h)=f\circ h$) – rnrstopstraffic Apr 6 '15 at 17:21
• @rnrstopstraffic Yeah, thanks. I forgot to mention the operation of composition $o$ in my comment... I think I understand now (at least the parts I needed ;) ). Thanks Paŭlo, great answer as usual. – Maarten Bodewes Apr 6 '15 at 17:22
• The associativity holds for the composition operation. Yes, $f^n(x)$ is perfectly fine when there is no danger of mixing it with $(f(x))^n$. (I added some text about this). – Paŭlo Ebermann Apr 6 '15 at 17:34