2
$\begingroup$

I have found in a Wireless Sensor Networks security paper, operations where cryptographic hash functions are elevated to the power of 2 and to the power of 3 (i.e. $h^2(x)$ and $h^3(x)$).

This might be a very simple question but I haven't found this notation in other literature. I wonder: does this notation mean that you need to compute the hash twice or thrice (i.e. $h(h(x))$ and $h(h(h(x)))$?

In the paper, $h$ is defined as a collision free one-way hash function.

$\endgroup$
  • 6
    $\begingroup$ Yes. ${}{}{}\;$ $\endgroup$ – user991 Apr 6 '15 at 10:16
5
$\begingroup$

Yes, these notations always seem to mean that H^n(x) (or $H^n(x)$ in mathematical notation) means that $x$ is the first input, and that the next outputs are a hash of the previous output:

H^0(x) = x           // just defined as x below
H^1(x) = H(x)
H^2(x) = H(H^1(x)) = H(H(x))
H^3(x) = H(H^2(x)) = ... = H(H(H(x)))
H^4(x) = ............... = H(H(H(H(x))))
...

so another way to define it is $H^n(x)=H(H^{n-1}(x))$ where $H^0(x)=x$. I've used uppercase H as that seems to be more common.

The construct seems to comply with the exponentiation property within abstract algebra as only the less strong power associativity is required for the function composition of the (hash) functions (beware - the answer on the math site requires some mathematical background).


Usually this kind of construction is used for key stretching; a method of calculating a key from a password (or other low entropy secret) that includes a work factor. In other words, both the user and an attacker are required to perform a number of operations, which makes attacking the password harder.

$\endgroup$
  • 1
    $\begingroup$ This is common notation in mathematics in general, not just crypto. $\endgroup$ – cpast Apr 6 '15 at 13:56
  • $\begingroup$ I've asked if this notation is mathematically correct here (on the math site) $\endgroup$ – Maarten Bodewes Apr 6 '15 at 16:07
  • 1
    $\begingroup$ I'm not sure what you're talking about with associativity. Associativity is a property of binary operations; a hash is not a binary function. Associativity isn't a thing with unary functions. Composing iterated hash functions is a binary operation, but that's associative in every sense. $\endgroup$ – cpast Apr 6 '15 at 16:30
  • $\begingroup$ @cpast Paŭlo explainted this nicely on the math site, seems you are right about the above comment. I won't copy Paŭlo's answer in though, I guess that's a bit too much for the less mathematically inclined. $\endgroup$ – Maarten Bodewes Apr 6 '15 at 17:27

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.