可忽略函数

可忽略函数是一个实值零序列，它趋于零的速度比任何多项式的倒数都快。 尽管术语可忽略序列更合适，但很少使用。 可忽略数en 用于密码学中的渐近考虑，以正式描述非常小的概率。

如果满足以下条件，函数 f : N → R被称为可忽略函数：

对于每个正多项式 p {dISPlaystyle p} 都有一个阈值 m p {diSPlaystyle m_{p}} m p {displaystyle n>m_{p}} 成立：

| f ( n ) | < 1 p ( n )

任何呈指数趋于零的序列，例如 B. f ( n ) = 1 2 n ，可以忽略不计。

另一方面，序列 f ( n ) = 1 q ( n ) 对于一个固定的正多项式 q 或 f ( n ) = 1 log 2 ⁡ ( n ) 不可忽略。

在可证明的安全性中，如果来自该类的每个攻击者只能以安全参数中至多可忽略的概率破坏安全性，则认为系统已经实现了针对攻击者类的安全目标。

如果任何多项式攻击者只能以可忽略的概率区分任意两个消息的加密，则公钥加密是 IND-CPA。 这里的概率取决于安全参数，它也决定了密钥的长度。 实际上，这意味着增加安全参数会大大降低攻击者成功的可能性。