前言
最近写的东西似乎很乱，一来是在看BIU密码学冬令营，基本上是看到哪儿就写到哪儿，比较随性，二来是疫情确实没啥心情干正事儿，而且好像快要上课了，心情也比较烦躁
不过每一篇文章讲的东西都相对独立一些，而且感觉有些知识不展开来写会误导大家，所以还是花些时间把这方面写清楚比较好
本篇主要讲的是不可区分性与单向函数，这两个概念在构建零知识协议和黑盒零知识中算是基础知识，但是并不会讲得太深，有误劳烦指出
统计不可区分性
Statistical Indistinguishability，统计零知识的一些前置知识，尽量讲明白一些
假设X和Y是集合Ω中随机选取的两个随机变量，则定义以下两个不可区分
- 完全不可区分（Perfect Indistinguishability）：对于任意的Ω的子集T，X∈T的概率与Y∈T的概率相等，也就是满足下面这个等式
$$ \forall T ⊆ \Omega\ ,\ Pr[X\in T]=Pr[Y \in T] $$
此时称X和Y完全不可区分，记为$X ≌ Y$
关于这里，想借用一下@宇哥考研在概率第一章讲的例子，可能会更好的帮助理解
有一个神奇的操场，天上会随机的掉馅饼到操场上，这时候一个同学拿盘子去接馅饼，从统计学的角度来说，这个同学接到馅饼的概率和他拿的盘子的大小成正比，也就是盘子的面积/操场的面积，盘子越大则接到馅饼的概率越大
回到上面的定义，全集Ω就是例子中的操场，子集T就是同学拿的盘子，对于天上随机掉下的馅饼X和Y，馅饼落入盘子T中的概率应该是相等的，和这个同学站在哪里没有关系，都是盘子的面积/操场的面积，也就是X和Y完全不可区分
这里的X和Y完全不可区分和子集的大小没关系，也就是说和盘子的大小没有关系，无论盘子大还是小（子集T的大小），两个馅饼落到盘子里的概率都是相等的，而且就算T是空集也行，空集的话说明两个概率都是0，那必然是相等的
- ε-不可区分（ε-Indistinguishability）：上面的完全不可区分似乎太严格了，因此放宽一些
对于任意的Ω的子集T，X∈T的概率与Y∈T的概率的差值小于等于一个数ε，也就是满足下面这个等式
$$ \forall T ⊆ \Omega\ ,\ |\ Pr[X\in T]-Pr[Y \in T]\ |\leqε $$
此时记为$X ≌_s Y$，下标为S（而不是ε）
还是上面这个馅饼的例子，假设馅饼X很重，是个铁饼，不会被风吹动，馅饼Y比较轻，会被风吹动（馅饼Y用红色表示，以和上面的区分）
那么对于同学而言，风吹不动馅饼X，如果馅饼本来不会落在盘子里的，那确实不会落在盘子里，如果馅饼Y本来不会落在盘子里的，经过风一吹，就可能落在盘子里了，那馅饼X和馅饼Y落在盘子里的概率就不一样了，也就不是上面的完全不可区分了
经过统计，他们俩概率的差不会超过一个数ε，那么称X和Y是ε-不可区分的
由于协议使用的是图灵机，图灵机的输入都是串，如果串的长度是n，那上述提到的X和Y就是长度为n的随机变量，记为X~n~和Y~n~，此时ε就是关于n的一个值，记为ε(n)
对于ε-不可区分，其有一些有趣的性质
- ε-不可区分的三角不等式：如果X和Y是ε~1~-不可区分，Y和Z是ε~2~-不可区分，那么X和Z是(ε~1~+ε~2~)-不可区分的
- 乘积形式：如果X和Y是ε-不可区分的，则X^q^和Y^q^是qε-不可区分
- 混合形式：
$$ if X ≌_s Y,then X^{q-i}XY^{i-1} ≌_S X^{q-i}YY^{i-1} $$
不难看出，第一个性质表明了ε-不可区分有传递的性质（或者说更类似一种累积的性质），多个ε-不可区分的变量之间不可区分的程度应该是累积的
后面两个性质大家可以试着理解，有能力的可以证明一下，对于随机变量的乘积，其不可区分的程度是成倍的增加的
单向函数
One-way Function，简单来说，单向函数是一种易于计算函数值，而在一般情况下难于求逆的函数
这个说法可以用砸玻璃类比，砸碎一块玻璃很简单，但是把玻璃渣恢复成一块完整的玻璃在一般情况下是不可行的（至少徒手不可行），或者说火柴燃烧，烧很简单，把五氧化二磷再捏回成就很难了
讨论单向函数目的是为了构造通常情况下难破译的问题（之后讲零知识会用到），还有就是用于构造单向陷门函数，单向函数在一般情况下难破译，但是不能直接用作密码体制，因为这样对于合法用户来说也难以破译了，因此缺乏普遍实用性，如果构造一个陷门，使得知道陷门的用户可以很快的解决这个问题，那对合法用户来说就非常友好了（单向陷门比较恰当的例子就是RSA）
需要注意的是，这里讨论的是单向函数，平时我们常见的SM2，MD5，SHA系列等hash函数，这些属于单向散列函数（或者是密码学安全hash函数），这些函数属于单向函数的候选者（candidate），但是真正的单向函数是否存在，目前仍然不知道，如果单向函数存在，会间接的表明P≠NP
接下来简单介绍一下几种单向函数
强单向函数
就是易于计算但是难于求逆的函数，一般提到单向函数，除非特别说明，一般都指代强单向函数
易于计算的意思就是存在一个多项式时间算法$f(x)$，当输入为$x$时，输出为$f(x)$，很好理解
但是第二个条件，求逆指的是对于给定输入$y$，求在$f$作用下$y$的逆元，难的意思是，即便是采用PPT算法，能够成功的概率也是可以忽略的(对$|y|$而言)
下面给出强单向函数的定义
若函数$f:{\{0,1\}}^* → {\{0,1\}}^*$，满足下列两个条件，则称函数$f$为（强）单向函数
- 易于计算：存在一个（确定的）多项式时间算法$A$，对于输入为$x$时，$A$的输出为$f(x)$，也即$A(x)=f(x)$
- 难于求逆：对于任意的PPT算法$A'$，任意的正多项式$poly \ p(\bullet )$，以及足够大的n，都有
$$ Pr[\ A'(f(U_n),1^n)\in f^{-1}(f(U_n)) \ ]<\frac{1}{p(n)} $$
第二个条件中的不等式里面的U~n~，指的是服从${\{0,1\}}^*$上均匀分布的一个随机变量，不等式的意思是对于任意的PPT算法$A'$，其找到$f(x)$的原像的概率是一个可忽略分数（可忽略分数也就是$<\frac{1}{p(n)}$，反之有显著分数，也即$>\frac{1}{p(n)}$)
需要注意的是，这里不要求找到$f(x)$的特定原像，如果$f$不是一对一映射的，那么找到一个原像即可，如果$f$是一对一映射的，那就要求找到那个唯一的原像（一般情况下$f(x)$会有其他的原像）
第一个条件好理解，第二个条件看不懂没关系，简而言之就是，对于任何高效的求逆算法而言，其成功概率的上界仍然是可忽略的
强单向函数的定义似乎太强太严格了，以至于求逆成功的概率都可以忽略，那么提供一种比较弱的定义，即弱单向函数
弱单向函数
强单向函数要求难于求逆，但是弱单向函数只要求稍微有点难求逆即可
若函数$f:{\{0,1\}}^* → {\{0,1\}}^*$，满足下列两个条件，则称函数$f$为弱单向函数
- 易于计算：存在一个（确定的）多项式时间算法$A$，对于输入为$x$时，$A$的输出为$f(x)$，也即$A(x)=f(x)$
- 稍微有点难求逆：存在一个多项式$poly \ p(\bullet)$使得对于任意PPT算法$A'$和任意足够大的n，都有
$$ Pr[\ A'(f(U_n),1^n)\notin f^{-1}(f(U_n)) \ ]>\frac{1}{p(n)} $$
其中第一个条件和强单向函数的第一个条件是一样的
第二个条件说明，存在一个多项式$p(n)$，求逆算法失败的概率下界为$\frac{1}{p(n)}$
对比一下强单向函数和弱单向函数，强单向函数表明，即便是求逆算法可以成功，其概率都是可忽略的，弱单向函数指的是，求逆失败的概率有一个确定的下界
换句话说，弱单向函数要求所有高效求逆的算法以一个显著的概率失败
一些候选的单向函数
目前仍然不知道单向函数是否真的存在，现在有一些单向函数的候选形式，但是仍然不知道这些函数是不是单向的
对于这些函数，目前仍然没有找到有效的求逆的算法，但是存在一些相对好使的成功概率算法
整数分解
目前分解整数最优秀的算法时间复杂度为亚指数，因此基于整数分解难题的如Rabin密码，RSA算法被认为是单向的
离散对数问题
如Elgamal，ECC等问题，都是基于离散对数问题，目前相对快速的算法如pollard ρ算法，时间复杂度也在根号级别
格上困难问题
如SVP、SIS、LWE等问题
AES
使用指定的密钥加密一个全零的串，也具有一定的难求逆性，不过这个难求逆性取决于使用的密钥
密码学安全的Hash函数
比如SM2，或安全性大于等于SHA256的Hash函数
其他
如译随机线性码，子集和问题等
后记
一边摸鱼一边写完的一篇博客，主要是在宿舍效率太低了（其实是想网瘾），参考了一下wiki和BIU冬令营，目前还处于可以理解的阶段，慢慢可能就看不懂了
慢慢来吧，这个方向比较复杂，30天学完别人琢磨了三十年的知识体系显然不现实
本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正
参考文章
$[1]$ The 9th BIU Winter School on Cryptography | BIU Cyber Center
$[2]$ Wiki-One-way_function
$[3]$ Wiki-Natural_proof
$[4]$ （英）Wenbo Mao著；王继林，伍前红等译.现代密码学理论与实践$[M]$.北京：电子工业出版社.2004.
$[5]$ （以）Odeb Goldreich著；温巧燕，杨义先译.密码学基础$[M]$.北京：人民邮电出版社.2003.