Hash Functions

1. Basic Definitions

Hash functions are a simple materialization of one-way functions, easy to compute in one way, very hard to reverse.

More formally we define them as follows:

$$H(x): \{0,1\}^* \rightarrow \{0,1\}^n $$

Generally, “good” hash functions are assumed to have the following traits (we describe these interactively):

Pre-image Resistance:

• you get $H(x) = y_0$ where $x$ is unknown
• find $x_0$ such that $x_0 = H^{-1}(y_0)$

flowchart LR
    subgraph you get
    y0
    end
    subgraph find
    x0
    end
    x0 --> y0
    x1 --> y1
    xn --> yn

Second Pre-image Resistance:

• you get a pair $(x_0,y_0)$ s.t $y_0=H(x_0)$
• find another value $x_1$ that yields $H(x_0)=H(x_1)$

flowchart LR
    subgraph you get
    direction LR
      x0 --> y0
         
    end
    subgraph find
      x00 --> y0
    end
    x1 --> y1
    xn --> yn

Collision Resistance

• you get nothing
• find two values $x_0$ and $x_1$ that yield $H(x_0) = H(x_1)$

flowchart LR
    subgraph find
      x0
      x00
    end
     x0 --> y0
      x00 --> y0
    x1 --> y1
    xn --> yn

What do we mean by hard to find? Typically exponential effort to find. For $n$ the size of the digest (result of a hash function) we define:

…