Ch5-Hash-Functions-and-Application.md

1. 哈希函数定义

将较长的字符串映射到较短的字符串，并且防止碰撞。

考虑包含密钥 $s$ 的哈希函数$H^s(x):=H(s,x)$. 有些情况下要求在密钥保密的情况下抗碰撞，有些情况下要求就算密钥公开也要抗碰撞。

定义 1.1 一个哈希函数（输出长度为 $l$）由两个概率多项式时间的算法 $(Gen, H)$ 构成：

1. $Gen:$ 输入安全参数$1^n$, 输出密钥 $s$.
2. $H:$ 输入 $x \in {0,1}^*$, 以及密钥 $s$, 输出$H^s(x) \in {0,1}^{l(n)}$.

考虑如下游戏：

1. 挑战者运行 $Gen(1^n)$ 得到密钥$s$.
2. 挑战者将密钥$s$给攻击者A（攻击者能计算任意$H^s()$ 值），输出$x,x'$.
3. 攻击者宣布成功当且仅当 $x \neq x'$ 且 $H^s(x) = H^s(x')$.

将上述游戏中攻击者成功的事件记为$S$, 则哈希函数抗碰撞当且仅当$Pr[S] \leq negl(n)$.

2. 定义域扩张：Merkle-Damgard Transform(MDT)

假设存在输入长度固定的抗碰撞哈希函数$(Gen,h)$, 构造任意输入长度的抗碰撞哈希$(Gen, H)$:

构造2.1：

$(Gen,h)$ 的输入长度为$2n$, 输出长度为$n$. 构造新的哈希函数$(Gen, H):$

1. $Gen$ 与原来一致。
2. $H$输入密钥$s, x \in {0,1}^*$, $|x|=L < 2^n$
   1. 令$B = \ulcorner \frac{L}{n} \urcorner$, 对$x$进行填充使其为$n$的倍数，获得$B$个长度为 $n$ 的字符串$x_1, x_2,...,x_B$. 令 $x_{B+1} = L$, $L$编码为长度为$n$的字符串。
   2. 令$z_0=0^n$.
   3. $i=1,...,B+1$, 计算$z_i:=h^s(z_{i-1}||x_i)$.
   4. 输出$z_{B+1}$.

**定理2.2：**如果$(Gen, h)$是抗碰撞的，那么$(Gen,H)$也是抗碰撞的。

Proof of Theorem 2.2:

假设攻击者$A$能在多项式时间内找出$H$的碰撞，我们构造新的攻击者$A'$找出$h$的碰撞。

攻击者$A'$

1. 均匀选取$s \leftarrow {0,1}^n$, 交给攻击者$A$.
2. 攻击者$A$输出$H$的碰撞$x,x'$,其中$|x|=L,|x'|=L'$.
3. 将 $x$ 分成 $x_1,..., x_B$, $x'$分成 $x'1,...,x'{B'}$.
4. 计算 $H^s(x), H^s(x')$记录下中间结果$z_1,...,z_B,z'1,...,z'{B'}$, 令$I_i=z_{i-1}||x_i, I_{B+2} = z_{B+1}$.
5. 若$L \neq L'$, 输出 $I_{B+1}, I'_{B'+1}$.
6. 若$L = L'$, $B = B'$ 假设$N$为最大值使得$I_N \neq I'{N}$, 注意到$I{B+2} = I'_{B+2}$, 所以$N \leq B+1$. 此时输出$I_N, I'_N$.

注意到如果$A$是概率多项式时间的，那么$A'$也是。

Case 1: 如果$L \neq L'$, 那么$I_{B+1} =z_{B}||x_{B+1} = z_{B}||L$ 以及 $I'{B'+1}=z'B||x'{B'+1} = z'B||L'$. 所以$I{B+1} \neq I{B'+1}$. 又$H^s(x)=H^s(x')$, 所以，$h^s(I_{B+1}) = h^s(I'{B'+1})$. 也就是说 $I{B+1}$ 和 $I'_{B'+1}$发生了碰撞。

Case 2: 如果$L=L'$, 那么$N$为最大值使得$I_N \neq I'{N}$, 所以$I{N+1} = I'{N+1}$. 也就是说$z{N} = z'_{N}$，又$z_N=h^s(I_N), z'_N=h^s(I'_N)$. 所以得出碰撞$I_N, I'_N$.