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; when $∣ R ∣/∣ D ∣$ is negligible, this implies one-wayness — RS04.

Syntax

A hash function is a function $H : K \times D \to R,$ where $K$ is the key space, $D$ is the domain, and $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 $H$ is one-way or preimage resistant if for every efficient $A,$

Adv_{H, A}^{pr} (λ) := Pr [G_{H, A}^{pr} (λ) = 1]

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

Auxiliary-input one-wayness

A function $f (x, \cdot)$ , efficiently computable given the auxiliary input $x$ , is auxiliary-input one-way if for all efficient $A$ there are infinitely many $x$ on which $A$ inverts $f (x, \cdot)$ on a uniform input with probability negligible in $∣ x ∣$ — OW93.

Weak one-wayness

A function $f$ is weakly one-way if there is a polynomial $p$ such that for all efficient $A$ and all sufficiently large $λ$ , $Adv_{f, A}^{pr} (λ) \leq 1 - 1/ p (λ)$ : every efficient inverter fails with noticeable probability — Yao82a. Every one-way function is weakly one-way, and weak one-way functions yield one-way functions.

Distributional one-wayness

A function $f$ computable in polynomial time is distributionally one-way if there is a polynomial $p$ such that for all efficient $A$ and all sufficiently large $n$ ,

Δ ((x, f (x)), (A (f (x)), f (x))) \geq 1/ p (n), x \leftarrow $ {0, 1}^{n},

where $Δ$ is statistical distance; equivalently, the statistical distance between $A (y)$ and a uniform element of $f^{- 1} (y)$ , averaged over $y = f (x)$ , is at least $1/ p (n)$ — IL89. Every one-way function is distributionally one-way — folklore; conversely, distributional one-way functions yield one-way functions — IL89.

Sub-exponential one-wayness

A function $H$ is sub-exponentially one-way if there is a constant $ε > 0$ such that for all sufficiently large $λ$ , every adversary $A$ of size at most $2^{λ^{ε}}$ has $Adv_{H, A}^{pr} (λ) \leq 2^{- λ^{ε}}$ .

Size-verifiable one-wayness

A one-way function $f$ is size-verifiable if the preimage-size problem ${(y, s) : ∣ f^{- 1} (y) ∣ = s}$ lies in $AM$ — AGGM06, BB15. It is approximately size-verifiable, a weaker condition, if the promise problem with yes-instances $(y, s, 1^{a})$ such that $∣ f^{- 1} (y) ∣ \leq s$ and no-instances $(y, s, 1^{a})$ such that $∣ f^{- 1} (y) ∣ > (1 + 1/ a) s$ lies in $AM$ — BB15. A one-way permutation is size-verifiable, since every $y \in {0, 1}^{n}$ has exactly one preimage — standard. A size-verifiable one-way function is a one-way function.

Collision resistance

Often times, protocols require stronger properties than one-wayness alone. When $∣ R ∣/∣ D ∣$ is negligible, collision resistance implies preimage resistance, but not conversely — RS04.

\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 compressing family $H$ with $D = {0, 1}^{n (λ)}$ and $R = {0, 1}^{m (λ)}$ , $m (λ) < n (λ)$ , is collision resistant, a collision-resistant hash function (CRHF), if for every efficient $A,$

Adv_{H, A}^{cr} (λ) := Pr [G_{H, A}^{cr} (λ) = 1]

is negligible. Compression is part of the definition because without it the notion is trivial: the identity has no collisions. The amount of compression is immaterial: Merkle–Damgård iteration turns a family compressing by one bit into a collision-resistant family from ${0, 1}^{p (λ)}$ to ${0, 1}^{m (λ)}$ for every polynomial $p$ — Dam89.

Target collision resistance (universal one-wayness)

The adversary commits to a target input before the key is sampled, then must find a second input colliding with it.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{tcr}}_{\hash,\calA}(\secpar)$}
\begin{algorithmic}
\State $(x, \st) \gets \calA_1(1^\secpar)$
\Comment{$\calA_1$ outputs $x \in \calD$ before seeing the key}
\State $k \getsr \calK$
\State $\hat{x} \gets \calA_2(\st, k)$
\Return $[\hash(k,\hat{x}) = \hash(k,x) \wedge \hat{x} \neq x]$
\end{algorithmic}
\end{algorithm}

A compressing family $H$ ( $∣ R ∣ < ∣ D ∣$ ) is a universal one-way hash function (UOWHF), or target collision resistant, if for all efficient $A = (A_{1}, A_{2})$ ,

Adv_{H, A}^{tcr} (λ) := Pr [G_{H, A}^{tcr} (λ) = 1]

is negligible — NY89. Collision resistance implies target collision resistance — standard.

Distributional collision resistance

Other results

Unknown results

Whether one-way functions imply collision-resistant hash functions is open. No relativizing construction exists, even from one-way permutations (No relativizing reduction from OWP to CRHF) — Sim98.

Participates in

Builds on Hash function

Produces Hash function

Barriers

Cryptology City

Explorer