Properties of a cryptographic hash function
A hash function $h(M)$ takes as input a message $M$ of any length and outputs a message digest or hash value of a fixed length, $n$. For a given message $M$, the output is always the same.
In mathematical notation, we write
$h: \{0,1\}^{*} \rightarrow \{0,1\}^n$, where $\{0,1\}^n$ represents a bitstring of length $n$.
A cryptographic hash function has the following three properties
- Preimage resistance
- Given $h(M) = x$ it is computationally infeasible to compute $M$.
- Second preimage resistance
- Given $h(M) = x$ it is computationally infeasible to find a message $M' \ne M$ such that $h(M') = x$.
- Collision resistance
- It is computationally infeasible to find two messages $M_1$ and $M_2$ such that $h(M_1) = h(M_2)$.
If the message digest length is $n$ bits, the time complexity of a preimage or second preimage attack is $2^n$. But the time complexity of a collision attack is only $2^{n/2}$ (using a birthday attack).
Therefore resistance against a collision attack (strong collision resistance) requires a hash value at least twice as long as that required for preimage resistance (weak collision resistance).
Note that SPHINCS+ is not affected by a collision attack against the hash function.
| << previous: SPHINCS+ A stateless hash-based signature scheme | Contents | next: One-time signature (OTS) scheme >> |
Contact us
To comment on this page or to contact us, please send us a message.
This page first published 17 March 2023. Last updated 9 September 2025.
