可忽略函数

可忽略函数不只是“很小”，而是随安全参数理路安全参数Security parameter共同索引密码算法族、资源规模与失败概率的渐近尺度。增长，比任何固定逆多项式都衰减得更快。量词顺序是：对每个常数 $c>0$，存在可依赖 $c$ 的阈值 $N_c$，使所有 $n>N_c$ 都有 $\mu (n)<n^{-c}$。固定有限个可忽略量可直接求和；若要累加多项式个随参数变化的量，还需要统一界。

$2^{-\lambda }$、$2^{-\sqrt{\lambda }}$ 和 ${\lambda }^{-\log \lambda }$ 都可忽略；$1/{\lambda }^{100}$ 不可忽略，因为取 $p(\lambda )={\lambda }^{101}$，也就是 $c=101$ 后，它并不最终小于 $1/{\lambda }^{101}$。固定常数 ${10}^{-100}$ 或 $2^{-128}$ 作为安全参数的函数也不可忽略，尽管工程上可能极小。定义只约束充分大的参数，有限多个异常点无关紧要。

以 $2^{-\sqrt{\lambda }}$ 为例，与 ${\lambda }^{-c}$ 比较并取二进制对数，只需检查 $\sqrt{\lambda }>c{\log }_2\lambda$。左侧最终压过右侧，所以每个固定 $c$ 都存在阈值；但阈值随 $c$ 改变，定义没有给出一个适用于所有 $c$ 的统一起点。

“趋于零”远弱于可忽略，例如 $1/\log n$。若把可忽略函数乘以指数因子，结果未必仍可忽略；安全归约只允许多项式损失正是为了保留这一性质。

“多项式个可忽略函数之和可忽略”并非无条件成立。例如令 ${\mu }_i(n)=1$ 当 $n=i$，其余时为 $0$；每个固定 $i$ 的 ${\mu }_i$ 都只有有限支撑，但 $\sum _{i=1}^n{\mu }_i(n)=1$。正确的统一版本是：若指标集 $I_n$ 的大小至多为多项式 $p(n)$，且存在同一可忽略函数 $\mu$ 使所有 $i\in I_n$ 均有 ${\mu }_i(n)\le \mu (n)$，则 $\sum _{i\in I_n}{\mu }_i(n)\le p(n)\mu (n)$ 仍可忽略。

可忽略量用于界定密码方案失败概率、实验优势理路安全实验、对手与优势函数Security experiment · Security game · Adversarial advantage以参数化交互实验和输出概率差精确定义攻击目标与对手能力的证明框架。和分布 ensemble 的统计距离。在计算不可区分理路不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。中，它约束每个固定 PPT 判别器的优势；在统计不可区分理路统计不可区分性Statistical indistinguishability · Information-theoretic indistinguishability两个分布族即使面对计算无界的判别器，其最优区分优势也随安全参数可忽略。中，它约束采用 $1/2$ 规范的总变差距离。具体对手接口和获胜事件仍由各安全游戏定义，本页只提供共同的渐近误差尺度。

在混合论证中，若步数至多为 $p(n)$，每一步的优势都由同一 $\mu (n)$ 控制，总优势才可以稳妥地界为 $p(n)\mu (n)$。“对每个攻击者都很小”也不能随意换成一个同时支配所有攻击者的全局界。

计算安全理路计算安全Computational security仅要求任何资源受限攻击者的成功优势足够小的安全概念。 用它限定攻击优势，不可区分性理路不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。 与 语义安全理路语义安全Semantic security · Computational semantic security密文不让多项式时间攻击者显著获得明文任何可计算信息的安全性。 都把失败概率压到该尺度；混合论证理路混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。 则系统地使用上一段的统一上界条件。