公钥密码学的基础概念比较驳杂，有些东西理解起来很简单，有些东西理解起来不太直观，部分概念牵涉到计算复杂性的理论。我在博文里面新开了一个categorie:公钥密码学的基础概念，以后遇到不同的就会慢慢更新，如果我有新的理解也会慢慢更新，当然这个categorie里的博文我不会写的特别详细，有些非常简单的东西我就直接略过了，可能没有公钥密码基础的同学读起来比较困难。

可忽略函数

    一个可忽略函数$f: \mathbb{Z} \mapsto \mathbb{R}$满足：对于任何$c>0$，存在一个$N_0>0$，当$\lambda>N_0$时，有$f(\lambda)< \frac{1}{\lambda^c}$。

    概念非常简单，有大一高数基础就可以看懂，可忽略函数一般记做$negl(\lambda)$。虽然概念简单，但可忽略这个概念非常重要，是定义密码方案安全性的重要基础，也就是要求方案成功“破解”的概率可忽略。比较常见的可忽略函数有$2^{-\lambda}, 2^{-\sqrt{\lambda}}, \lambda^{-log\lambda}$。

不可分辨

    实际上不可分辨和以前的计算不可区分没有多大区别，只是这里为了在公钥密码里应用的更方便，区分算法(或者分辨算法)是一个分辨实验或者分辨game。
    首先给定两个随机分布总体$\mathcal{X}$和$\mathcal{Y}$

$$\mathcal{X}:=\lbrace \mathcal{X}_\lambda \rbrace_{\lambda \in \mathbb{N}}$$ $$\mathcal{Y}:=\lbrace \mathcal{Y}_\lambda \rbrace_{\lambda \in \mathbb{N}}$$

对敌手$\mathcal{A}$，任意$b\in\lbrace 0,1 \rbrace$，可以进行下面的分辨实验(安全参数为$1^\lambda$，标志着输入长度)

分辨实验$Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-b}(\cdot)$，输入$1^\lambda$

1，抽取$x_0 \leftarrow \mathcal{X}_\lambda , x_1 \leftarrow \mathcal{Y}_\lambda$，把$x_b$给$\mathcal{A}(1^\lambda)$
2，算法$\mathcal{A}(1^\lambda ,x_b)$输出一个比特$b’$
3，实验输出$b’$，实验结束

    如果敌手猜对$b$，即$b=b’$，则说敌手分辨成功。敌手分辨成功的优势$Adv_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-01}(\lambda)$定义为

$$Adv_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-01}(\lambda):=|Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =1]-Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1]|$$

如果任何$PPT$的敌手$\mathcal{A}$，分辨的优势均是$\lambda$的可忽略函数，则说$\mathcal{X}$和$\mathcal{Y}$是不可分辨的。

关于不可分辨的一些分析

不可分辨是渐近意义下的

    首先来看随机分布总体的概念，$\mathcal{X}:=\lbrace \mathcal{X}_\lambda \rbrace_{\lambda \in \mathbb{N}}$和$\mathcal{Y}:=\lbrace \mathcal{Y}_\lambda \rbrace_{\lambda \in \mathbb{N}}$是两个随机分布总体，$\lambda \in \mathbb{N} , \lambda$可以取成一个$\mathbb{N} \rightarrow \mathbb{N}$的函数$f(n)$，所以$\mathcal{X}$与$\mathcal{Y}$可以理解为两个随机分布序列

$$\mathcal{X} : \mathcal{X}_{f(1)},\mathcal{X}_{f(2)}, \cdots \cdots$$ $$\mathcal{Y} : \mathcal{Y}_{f(1)},\mathcal{Y}_{f(2)}, \cdots \cdots$$

当$\lambda$确定后$\mathcal{X}_\lambda$与$\mathcal{Y}_\lambda$是一个分布，比如$\mathcal{X}_\lambda$与$\mathcal{Y}_\lambda$可以都是上$\{ 0,1\}^\lambda$的分布，所以给了一个$\lambda$只是从分布序列里确定了某一个分布。

    所以$\mathcal{X}$与$\mathcal{Y}$不可分辨是渐近性质的，$Adv(\lambda)$可忽略，即任意$c>0, \exists N_0>0 ,s.t. \lambda >N_0$时有$Adv(\lambda) \leq \frac{1}{\lambda^c}$，所以$\lambda$比较小时，$Adv(\lambda)$不一定很小，可能还比$\frac{1}{\lambda^c}$大，所以说$Adv(\lambda)$是渐近性质的，当$\lambda$逐渐变大时，$\mathcal{X}$与$\mathcal{Y}$不可分辨。

优势的等价定义

    前面的定义里，算法$\mathcal{A}$成功的优势定义为：

$$Adv_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-01}(\lambda):=|Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =1]-Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1]|$$

实际上可以理解为敌手分辨成功的概率和分辨失败的概率之间的差距，这个差距越大，敌手就“越”能分辨。但实际上，这个优势还有一种定义方式，首先有：

$$\begin{aligned} Adv_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-01}(\lambda) &:=|Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =1]-Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1]| \\ &= |1-Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =0]-Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1]|\\ &= |Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =0]+Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1]-1| \end{aligned}$$

另外有：

$$Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =0]+Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1] =2(\frac{1}{2}Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =0]+\frac{1}{2}Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1]) \\ =2(Pr[b=0 ]Pr[ Expt success|b=0]+Pr[b=1 ]Pr[ Expt success|b=1])\\ =2Pr[ Expt success]$$

则有：

$$\begin{aligned} Adv_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-01}(\lambda) &:=|Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =1]-Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1]| \\ &= |1-Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =0]-Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1]|\\ &= |Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =0]+Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1]-1| \\ &=|2Pr[ Expt success]-1| \\ &=2|Pr[ Expt success]-\frac{1}{2}| \end{aligned}$$

所以优势也可以写成：

$$Adv_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-01}(\lambda) :=|Pr[ Expt success]-\frac{1}{2}|$$

所以可以发现这两种定义方式:

$$Adv_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-01}(\lambda):=|Pr[ Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-0}(1^\lambda) =1]-Pr[Expt_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-1}(1^\lambda) =1]|$$ $$Adv_{\mathcal{A},(\mathcal{X},\mathcal{Y})}^{ind-01}(\lambda) :=|Pr[ Expt success]-\frac{1}{2}|$$

实际上是完全等价的，只不过是相差了一个两倍的关系而已，具体使用时，哪一个更方便于证明就用哪一个。