形式陈述

函数 $\mu:\mathbb N\to\mathbb R_{\ge0}$$\mu :\mathbb{N}\to {\mathbb{R}}_{\ge 0}$ 称为可忽略的，若对每个正多项式 $p$$p$，存在 $N_p$$N_p$ 使得

$$ \lambda\ge N_p\quad\Longrightarrow\quad \mu(\lambda)<\frac1{p(\lambda)}. $$$$\lambda \ge N_p⟹\mu (\lambda )<\frac{1}{p(\lambda )}.$$

等价地，对每个常数 $c>0$$c>0$，最终有 $\mu(\lambda)<\lambda^{-c}$$\mu (\lambda )<{\lambda }^{-c}$。有限个可忽略函数之和、可忽略函数与多项式有界函数之积仍可忽略。

直觉

可忽略函数不仅“很小”，而是随着安全参数增长，比任意固定逆多项式都衰减得更快。这使多项式次数未知的攻击者仍无法通过多项式次重复把失败概率放大到常数量级。

例子与边界

$2^{-\lambda}$$2^{-\lambda }$、$2^{-\sqrt\lambda}$$2^{-\sqrt{\lambda }}$ 和 $\lambda^{-\log\lambda}$${\lambda }^{-\log \lambda }$ 都可忽略；$1/\lambda^{100}$$1/{\lambda }^{100}$ 不是，因为取 $p(\lambda)=\lambda^{101}$$p(\lambda )={\lambda }^{101}$ 即失败；常数 $10^{-100}$${10}^{-100}$ 也不是。定义只约束充分大的参数，有限多个异常点无关紧要。

推论与应用

可忽略量用于定义密码方案失败概率、攻击优势和统计距离。可数无穷个可忽略函数之和未必可忽略，且“对每个攻击者都很小”不能随意交换为存在一个统一忽略界，量词必须保留。

参考资料

• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020，§3.1。
• Oded Goldreich, Foundations of Cryptography, Vol. 1, Cambridge University Press, 2001，§2.2。