摘要函数其实就是$Hash$函数，只是叫法不一样而已，另外我们这里讨论的摘要函数一般都是函数族，而不是一个单个固定的函数，类似于拟随机函数的概念。在实际密码方案应用时，会先选定安全参数$\lambda$，然后由安全参数确定了一个函数集合，然后再输出一个函数索引，取出此索引对应的函数，这时这个函数就是确定的，然后让这个函数完成$Hash$函数的功能。

摘要函数具体定义

    一个摘要函数$HASH$由两个$PPT$算法$(HGen,H)$组成，满足：
$\color{red}{HGen}$：是一个$PPT$算法，输出安全参数$1^\lambda$，输出一个键值$s(\lambda)$
$\color{red}{H^s(\cdot)}$：是一个由键值$s(\lambda)$确定的函数，对于任意串$x \in \{0,1\}^*, H^s(x) \in \{0,1\}^l$。其中$l$是$\lambda$的整多项式。如果$H$的输入是某个集合$\{0,1\}^{l'(\lambda)}$，其中$l' \leq l$，这时的摘要函数称为是定长的摘要函数。

    这个定义也是非常直观的，由安全参数确定函数集合，然后再由安全参数确定函数索引(键值)，确定一个函数。

摘要函数的强抗碰撞性

    抗碰撞性是摘要函数非常重要的性质，也是摘要函数存在的基础，既然想对一个长的字符串生成摘要，那就要尽量避免两个不同的字符串却生成了相同的摘要，当然这样的“碰撞”必然是存在的，我们只是想这种碰撞不能被高效的找到。首先来看强抗碰撞性，为了给这种性质标准的密码学语言表示，还是要用到实验的思想：
找碰撞实验$\color{red}{Expt_{\mathcal{A},HASH}^{hashcoll}(1^\lambda)}$：
1，生成一个键值$s(\lambda) \leftarrow HGen(1^\lambda)$
2，敌手得到$s$后输出$x,x' \leftarrow \mathcal{A}(H^s,1^\lambda), x\neq x'$
3，输出1当且仅当$H^s(x)=H^s(x')$，否则输出0
    显然敌手$\mathcal{A}$是可以知道用了哪一个具体的摘要函数的，如果$HASH=(HGen,H)$满足：对任意$PPT$敌手$\mathcal{A}$都存在可忽略函数$negl$，使得

$$Adv_{\mathcal{A},HASH}^{hashcoll}(\lambda):=Pr[Expt_{\mathcal{A},HASH}^{hashcoll}(1^\lambda)=1] \leq negl$$

则称$HASH=(HGen,H)$为强的抗碰撞的摘要函数。

摘要函数的弱抗碰撞性

    摘要函数的弱抗碰撞性本质上就是去寻找第二原像，首先定义找第二原像的实验如下：
找第二原像实验$\color{red}{Expt_{\mathcal{A},HASH}^{tcr}(1^\lambda)}$：
1，生成一个键值$s(\lambda) \leftarrow HGen(1^\lambda)$和一个比特串$x\leftarrow \{0,1\}^*$
2，敌手得到$s,x$后输出$x' \leftarrow \mathcal{A}(H^s,1^\lambda), x\neq x'$
3，输出1当且仅当$H^s(x)=H^s(x')$，否则输出0
    显然敌手$\mathcal{A}$是可以知道用了哪一个具体的摘要函数的，如果$HASH=(HGen,H)$满足：对任意$PPT$敌手$\mathcal{A}$都存在可忽略函数$negl$，使得

$$Adv_{\mathcal{A},HASH}^{tcr}(\lambda):=Pr[Expt_{\mathcal{A},HASH}^{tcr}(1^\lambda)=1] \leq negl$$

则称$HASH=(HGen,H)$为弱的抗碰撞的摘要函数。

强与弱的不同

    首先这两个实验的优势与之前学过的不可分辨实验的优势有一些差别，那里都需要减去一个$\frac{1}{2}$，但这里实际上并不是分辨，只是找碰撞而已，找到了就成功，找不到就失败，所以才有优势就是成功的概率：

$$Adv_{\mathcal{A},HASH}^{hashcoll}(\lambda):=Pr[Expt_{\mathcal{A},HASH}^{hashcoll}(1^\lambda)=1] \\ Adv_{\mathcal{A},HASH}^{tcr}(\lambda):=Pr[Expt_{\mathcal{A},HASH}^{tcr}(1^\lambda)=1]$$

    另外强与弱的区分点是敌手的能力，强碰撞实验那里，只要敌手随便找到一个碰撞就行了，随便找到一个碰撞就认为敌手$\mathcal{A}$成功了，但第二个实验是说随便一个碰撞不行，必须是给定的$x$的碰撞$x’$才行，哪怕敌手找出一个碰撞$y$和$y’$也不行，所以第一个实验的摘要函数对敌手的限制少，但限制少依旧有找到碰撞可忽略，就叫强摘要函数，第二个实验限制多才安全，就叫弱摘要函数。显然强摘要函数一定是弱摘要函数，弱摘要函数不一定是强摘要函数。