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

• Hash function ⇒ PRG
• Hash function ⇒ Hash-based signatures
• PRF ⇒ PRP
• Hash-based signatures ⇒ DS
• OWP ⇒ Hash function
• No reduction from NP to Hash function

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.

Participates in

Builds on Hash function

• AE + Hash function + PRF ⇒ Symmetric CP-ABE
• Hash function + Hash-based signatures ⇒ DS
• Hash function + iO ⇒ Deniable encryption
• Hash function + iO ⇒ DS
• Hash function + iO ⇒ FE
• Hash function + iO ⇒ Lossy trapdoor functions
• Hash function + iO ⇒ NIZK
• Hash function + iO ⇒ PKE
• Hash function + PRF ⇒ Symmetric CP-ABE
• Hash function ⇒ CZK
• Hash function ⇒ DPF
• Hash function ⇒ DS
• Hash function ⇒ Hash-based signatures
• Hash function ⇒ Hash-based signatures
• Hash function ⇒ MAC
• Hash function ⇒ PCS
• Hash function ⇒ PRF
• Hash function ⇒ PRG
• Hash function ⇒ Secret-Key PIR (SK-PIR)
• Hash function ⇒ SKE
• Hash function ⇒ SNARK
• Hash function ⇒ ZKP

Produces Hash function

• DS ⇒ Hash function
• Noise Level ⇒ Hash function
• OWP ⇒ Hash function
• PKE ⇒ Hash function
• PRG ⇒ Hash function
• SIS ⇒ Hash function
• SNARK ⇒ Hash function
• Subclasses ⇒ Hash function
• TDP ⇒ Hash function
• ZKP ⇒ Hash function

Barriers

• No reduction from Fiat-Shamir + Hash function to DS
• No fully-black-box reduction from Hash function to PKE
• No reduction from NP to Hash function