Lecture 1.1: Cryptographic Hash Functions
Hash function:
1. takes any string as input;
2. fixed-size output;
3. efficiently computable;
Security properties:
1. collision-free;
What’s meaning?
Nobody can find $ x $ and $ y $ such that $ x!= y $ and $ H(x) = H (y) $；
Application?
Hash as message digest.
If we know $H(x) = H(y)$, it’s safe to assume that $x = y$. So we can just remember the hash to recognize a file that we saw before.
2. hiding;
What’s the meaning?
We want something like this: Given $H(x)$, it is infeasible to find $x$.
Application?
Commitment.
For commitment and verification, we can assign commit(msg) = (H(key | msg), key);
and the verify(commit, key, msg) will be true or false calculated by the expression H(key | msg) == commmit.
3. puzzle-friendly;
What’s the meaning?
For every possible output value $y$,
if $k$ is chosen from a distribution with high min-entropy,
then it is in feasible to find x such that $H(k | x) = y$ .
Application?
To build a search puzzle.
Puzzle-friendly property implies that no solving strategy is much better than trying values of x.