Hash functions

A hash function is function which can have a number of different properties in cryptography. Most often, it is required that the hash function is one-way or preimage resistant. If such a hash function exists, then many other primitives are known to exist. In other settings, it’s important that the hash function is collision resistant, meaning that it is hard to find two colliding inputs and implies one-wayness.

Syntax

A hash function is a function $\mathsf{H}:\mathcal{K}\times \mathcal{D}\to \mathcal{R},$ where $\mathcal{K}$ is the key space, $\mathcal{D}$ is the domain, and $\mathcal{R}$ is the range.

Properties

There are a number of different properties that different cryptographic protocols require of hash functions. Sometimes, even the particular assumptions are insufficient to prove security of a protocol. In this case, there is sometimes still hope to prove security when modeling a hash function as a random oracle.

Preimage resistance (one-wayness)

One of the most fundamental properties is preimage resistant or one-way. This is important in many computational complexity analyses.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{pr}}_{\hash,\calA}(\secpar)$}
\begin{algorithmic}
\State $k \getsr \calK$ ; $x \getsr \calD$
\State $y \gets \hash(k,x)$
\State $\hat{x} \gets \calA(k,y)$
\Return $[\hash(k,\hat{x}) = y]$
\end{algorithmic}
\end{algorithm}

A hash function $\mathsf{H}$ is one-way or preimage resistant if for every efficient $\mathcal{A},$

$${\mathbf{Adv}}_{\mathsf{H},\mathcal{A}}^{\mathrm{pr}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{H},\mathcal{A}}^{\mathrm{pr}}(\lambda )=1\right]$$

is negligible. In this case, $\mathsf{H}$ is called a one-way function (OWF).

Collision resistance

Often times, protocols require stronger properties than one-wayness alone. Collision resistant hash functions are strictly stronger than preimage resistance.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cr}}_{\hash,\calA}(\secpar)$}
\begin{algorithmic}
\State $k \getsr \calK$
\State $(\hat{x}_0, \hat{x}_1) \gets \calA(k)$
\Return $[\hash(k,\hat{x}_0) = \hash(k,\hat{x}_1) \wedge \hat{x}_0 \neq \hat{x}_1]$
\end{algorithmic}
\end{algorithm}

A hash function $\mathsf{H}$ is collision resistant if for every efficient $\mathcal{A},$

$${\mathbf{Adv}}_{\mathsf{H},\mathcal{A}}^{\mathrm{cr}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{H},\mathcal{A}}^{\mathrm{cr}}(\lambda )=1\right]$$

is negligible.

Distributional collision resistance

Other results

• If one-way functions exist, then many “Minicrypt” primitives exist, via the chain OWF → PRG (HILL99, GL89) → PRF (GGM86):
  • Symmetric Key Encryption
  • Pseudorandom Functions
  • Pseudorandom Permutations
  • Message Authentication Codes
  • Digital Signatures (via Lamport one-time signatures Lam79 + Merkle trees Mer89)
• One-way functions exist if OWPs exist
• Basing OWFs on worst-case NP-hardness is unlikely: any black-box reduction would imply a collapse of the polynomial hierarchy — AGGM06

Unknown results

• It is not known whether one-way functions imply collision-resistant hash functions; no black-box construction is known and oracle separations suggest this implication is unlikely.