可忽略的（和不可忽略的）功能到底是什么？

#1 楼

在像一次性垫这样的完全秘密的方案中，成功的概率不会随着更大的计算能力而提高。但是，在现代密码方案中，我们通常不会尝试实现完美的保密性（是的，政府可能会使用一个时限，但这对于普通用户而言通常不切实际）。实际上，考虑到无穷大的计算能力，我们所有的非完美秘密方案都是不安全的（还请注意，对于公钥加密，使用经典密码技术无法实现完美的保密性，因此所有方案都不受无限的计算能力的影响）。取而代之的是，我们针对计算能力有限的一组特定对手定义安全性。通常，我们假设一个对手必须在时间多项式上运行到$ n $，其中$ n $是提供给密钥生成算法的安全参数（更确切地说，密钥生成算法的输入为$ 1 ^ n $，因此$ n $将是其输入大小，其输出（键）将是其输入大小的多项式。）

所以考虑一个方案$ \ Pi $，这是对它的唯一攻击是蛮力攻击。如果$ \ Pi $不能被多项式时间内的蛮力攻击破坏，则认为它是安全的。

可忽略的概率这个概念包含了这个确切的概念。假设在$ \ Pi $中，我们有一个受多项式限制的对手。暴力攻击不是一种选择。但是，代替了蛮力，对手可以猜测随机值（的多项式），并希望抓住正确的值。在这种情况下，我们使用可忽略的函数定义安全性：成功的概率必须小于任何多项式函数的倒数。

这很有道理：如果单个猜测的成功概率是多项式函数的倒数，则对手可以尝试多项式猜测并以高概率成功。总之，如果总体成功率为$ 1 / poly（n）$，则我们认为这是可行的攻击，并且该方案是不安全的。

因此，我们要求成功概率必须小于每个多项式函数的倒数。这样，即使对手尝试了poly（n）的猜测，它也不会很重要，因为它只会尝试：

$$ \ mathit {poly}（n）/ \ mathit {superpoly} （n）$$

随着$ n $的增长，分母的增长远快于分子，成功的可能性将不大。

编辑添加来非正式的论点可能会更清楚：要了解超多项式暴力攻击和可忽略的概率猜测的概念是等效的，请考虑具有$ K $个可能键的方案。

对密钥集的强力攻击需要花费$ K $的时间。此外，随机选择一个密钥作为正确密钥的概率为$ 1 / K $。现在，如果$ K $是$ n $的多项式（安全性参数），则可以在$ K = \ mathit {poly}（n）$的时间内强行强制执行此方案。此外，随机猜测成功的概率为$ 1 / K = 1 / \ mathit {poly}（n）= \ text {non-negligible} $
，并且该方案在两个定义上都是不安全的。

然后为了确保方案安全，我们想让暴力行为在超多项式时间内运行。换句话说，$ K $必须是$ n $的超多项式。那么，一次猜测就可以正确猜测的概率为$$ 1 / K = 1 / \ mathit {superpoly}（n）$$，根据定义，这是可以忽略的概率。

尽管是非正式的，但我认为最后一部分鼓励在安全性证明中使用微不足道的功能。

#2 楼

尽管这是一个很好的解释，但我想补充一点，在其他证明中，您也会看到微不足道的功能。一个例子是peusdorandom字符串。如果攻击者查看字符串，则他只能确定该字符串是伪随机还是“真实”随机”，概率为（分布）$$½+ \ mathit {negl}（n）$$

他总是可以扔硬币（给他概率½），但也许他可以提取一些信息来“改善”他的猜测。