博主正在学习INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些笔记供自己回忆，如有错误请指正。整理成一个系列现代密码学，方便检索。

《现代密码学》第一章所介绍的古典密码，全都已经被破解了，由于没有严格的安全定义，无法证明安全性，第二章引入了完美安全的定义，是一种对于密码方案的安全性定义，但是满足这种安全性定义的密码方案具有一个共同缺点：密钥空间$|\mathcal{K}|$>明文空间$|\mathcal{M}|$，而且这种安全性往往是现实中难以达到的：无限算力的敌手+不能泄露丝毫明文信息。考虑实际需求，给出一种新的安全性定义：“计算安全/computational security”：有限算力的敌手+以极小概率泄漏明文信息。

三种安全性定义

相比于完美安全，还有两种安全性定义：计算安全和统计安全。

完美安全满足：

• 无限算力的敌手
• 不泄露丝毫明文信息

统计安全满足：

• 无限算力的敌手
• 以极小概率泄露明文信息

计算安全满足：

• 有限算力的敌手
• 以极小概率泄漏明文信息

完美安全偏向理论，计算安全和统计安全往往是实际中的安全性定义。

定义计算安全的两种方法

我们可以把计算安全看作对完美安全的放缩，有2点放缩：敌手算力+泄露明文的概率。现在需要去定义这样的放缩，有两种方式：具体方法和渐进方法。

具体方法/concrete approach

用具体数值表示放缩。

定义：如果任何敌手运行时间最长为$t$，攻破密码方案的概率最多为$ϵ$，则称该方案是$(t,ϵ)-$安全。

但这种方式其实是很难提供的。比如我们给一个声明：“最长运行5年，敌手攻破密码方案的概率最多为$ϵ$”，这样的定义伴随着诸多问题：

• 算力是多少？PC、超级电脑、网络都不同
• 随着未来技术的发展，算力也会发展，有考虑进来吗？
• 如果软件优化呢？
• 运行2年，攻破概率是多少？
• 运行10年，攻破概率是多少？

渐进方法/asyptotic approach

引入安全参数，用关于安全参数的函数来表示放缩。

由于具体方法定义安全性是很难提供的，那我们考虑用函数来定义安全性。引入一个安全参数$n$，用关于$n$的函数来定义敌手算力以及攻破概率。

定义：如果运行时间为关于安全参数$n$的概率多项式函数/PPT/probabilistic polynomial-time，攻破密码方案的概率是可忽略的/negligible，则称该方案是安全的。

引入安全参数，主要是在语法定义和安全性定义中起作用：

• 语法定义：生成密钥算法$Gen$、加密算法$Enc$、解密算法$Dec$都是关于安全参数的多项式时间函数；
• 安全性定义：敌手运行时间是关于安全参数的概率多项式函数，敌手攻破概率是关于安全参数的可忽略函数。

“高效/PPT”和“可忽略/negligible”

现在定义“概率多项式时间函数”和“可忽略函数”。

• 概率多项式时间函数：对于所有任意长度的01串$x\in \{0,1{\}}^{\ast }$，总存在一个多项式$p$，使得计算函数$A(x)$在$p(|x|)$步内终止，则称$p$是一个概率多项式时间函数。这是一个$BPP$问题类，其中$p\subseteq BPP\subseteq NP(P\ne NP$的前提假设)。
• 可忽略函数：对于任意多项式$p$，以及所有足够大的自然数$n$，函数$f$都满足$f(n)<\frac{1}{p(n)}$，则称$f$是可忽略函数。

理论上，我们考虑可忽略函数是考虑$n$为无穷大的情况；实际上，我们考虑$n$较小的情况。举个例子：

• $2^{-\sqrt{n}}$
• $n^{-\log n}$

考虑这两个函数，他们有

• $2^{-\sqrt{n}}<n^{-5}\to n=3500$
• $n^{-\log n}<n^{-5}\to n=33$

也就是说对于多项式$n^{-5}$来说，$2^{-\sqrt{n}}$需要$n>3500$才有可忽略性；$n^{-\log n}$只需要$n>33$就有可忽略性。这意味着$n^{-\log n}$更快逼近0。但是

• $2^{-\sqrt{n}}<n^{-\log n}\to n>65536$

$n>65536$时$2^{-\sqrt{n}}<n^{-\log n}$的意思是当我们考虑无穷大时，$2^{-\sqrt{n}}$是更接近0的。

也就是说，我们在理论上取$2^{-\sqrt{n}}$，是更合适的可忽略函数；但是实际上，我们只需取$n^{-\log n}$即可，在$n$较小时它逼近0的速度更快。