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.

  • 1
    $\begingroup$ Hash functions are unary. Associativity is a property of binary operations. $\endgroup$ – cpast Apr 6 '15 at 16:31
  • $\begingroup$ @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? $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Maarten Bodewes Apr 6 '15 at 17:16
  • $\begingroup$ +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$). $\endgroup$ – rnrstopstraffic Apr 6 '15 at 17:19
  • $\begingroup$ @MaartenBodewes the associativity holds for the operation of composition (which can be considered a binary function $g(f,h)=f\circ h$) $\endgroup$ – rnrstopstraffic Apr 6 '15 at 17:21
  • $\begingroup$ @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. $\endgroup$ – Maarten Bodewes Apr 6 '15 at 17:22
  • 1
    $\begingroup$ 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). $\endgroup$ – Paŭlo Ebermann Apr 6 '15 at 17:34

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.