Hash functions

A hash function is function which can have a number of different properties in cryptography. Most often, it is requried 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 casee, 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 computaitonal 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,y)$
\Return $[\hash(k,\hat{x}_0) = \hash(k,\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

Related results

• If one-way functions exist, then many “Minicrypt” primitives exist:
  • Symmetric Key Encryption
  • Pseudorandom Functions
  • Pseudorandom Permutations
  • Message Authentication Codes
  • Digital Signatures
• One-way functions exist if a OWPs exists

Unknown results

• It’s unkonwn if one-way functions imply collision resistant hash functions.