5 哈希函数¶
哈希函数是将任意长度的字符串压缩成短的字符串的函数。
函数中的碰撞是指有一对不同的输入量 \(x\) 和 \(x'\) 满足 \(H(x) = H(x')\)，这种情况也称作 \(x\) 和 \(x'\) 在 \(H\) 下发生碰撞。如果任何概率多项式时间的敌手在 \(H\) 中都不能发现碰撞，就称 \(H\) 是抗碰撞的。
Warning
对于具有无穷定义域和有限值域的函数或压缩输入量的函数，根据鸽巢原理，碰撞是必然存在的，因而要求仅仅是碰撞很难发现。
考虑密钥哈希函数（keys hash functions），\(H\) 是一个双输入参数的函数，输入一个密钥 \(s\) 和一个字符串 \(x\)，并输出一个字符串 \(H^{s}(x)\stackrel{\text{def}}{=}H(s,x)\)。
密钥 \(s\)
密钥 \(s\) 与我们先前使用的密钥至少有两处不同：
- 不是所有的字符串都需要对应有效的密钥，即 \(H^{s}(x)\) 可能对某些 \(s\) 没有定义，因此密钥 \(s\) 是由 \(\text{Gen}\) 算法产生，而不是均匀随机选取的
- 密钥 \(s\) 并不是保密的，只是用在一个特定的函数 \(H^{s}\) 中，为了强调这点，这里将它标在右上方，记为 \(H^{s}\) 而不是 \(H_{s}\)
-
哈希函数是一对概率多项式时间算法 \(\text{(Gen, H)}\)，满足如下条件：
- \(\text{Gen}\) 是一个概率算法，输入安全参数 \(1^n\) 并输出密钥 \(s\)（假设 \(1^n\) 隐含在 \(s\) 中）
- 存在一个多项式 \(l\) 满足：对 \(H\) 输入一个密钥 \(s\) 和一个字符串 \(x \in \{0,1\}^*\)，并输出一个字符串 \(H^s(x) \in \{0,1\}^{l(n)}\)（\(n\) 是隐含在 \(s\) 中的安全参数）
-
如果当输入 \(x \in \{0,1\}^{l'(n)}\) 和 \(l'(n) > l(n)\) 时 \(H^s\) 有定义，就称 \((Gen, H)\) 是输入长度为 \(l'(n)\) 的定长哈希函数。
碰撞发现实验 \(\text{Hash - coll}_{\mathcal{A},\Pi}(n)\)
- 运行 \(\text{Gen}(1^n)\) 得到密钥 \(s\)
- 敌手输入 \(s\) 并输出 \(x\) 和 \(x'\)（如果 \(\Pi\) 是输入长度为 \(l'(n)\) 的定长散列函数，我们要求 \(x,x' \in \{0,1\}^{l'(n)}\)）
- 当且仅当 \(x \neq x'\) 且 \(H^s(x) = H^s(x')\) 时，实验的输出被定义为 \(1\)，在这种情况下，称 \(\mathcal{A}\) 发现了一个碰撞
- 哈希函数 \(\Pi = (\text{Gen}, H)\) 是抗碰撞的，如果对于所有的概率多项式时间敌手 \(\mathcal{A}\)，存在着一个可忽略的函数 \(\text{negl}\)，满足
\[
\Pr[\text{Hash - coll}_{\mathcal{A},\Pi}(n) = 1] \leq \text{negl}(n)
\]