密码学中可忽略的功能

Question

在密码学和计算复杂性领域中，有一个可忽略的函数概念。

我在理解这个概念背后的直觉方面遇到了一些困难。以下是第9章的一些定义。教科书计算复杂性中的密码学。 Arora和Barak的现代方法，并广泛使用可忽略的功能。在每个定义上都可以忽略不计的问题之后，我的问题就在那里。

在进一步进行之前，我们进行了一个简单的定义，可以在本章中大大简化符号。

可忽略的功能的定义. 。一个函数$ epsilon： mathbb {n} rightarrow [0,1] $如果$ epsilon（n）= n^{ - omega（1）} $，则称为可忽略不计。

由于可忽略不计的功能往往会随着输入的增长而非常快地零，因此在大多数实用和理论设置中，可以安全地忽略概率可忽略的事件。

到目前为止，这只是对功能可忽略的定义，唯一的一点是，为什么我们需要关心此功能 “可以安全地忽略”。

计算安全功能的概念。$ k in_r {0,1 }^n，x in_r {0,1 }^m，pr [a（e_k（x））=（i，b）st x_i = b] leq frac {1} {2}+ epsilon（n）$。

对功能可忽略的直觉用法。正如我所知，通常，$ a $ a $ can含量为0.5猜测均匀分布的$ x_i $，因此，它使得预期的成功下降为$ leq leq frac {1} {2} {2} $，但是它是$ leq frac {1} {2} + epsilon（n）$，我们可以“安全地忽略” $ epsilon（n）$为什么要提及它，第二点是可以运行$ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $有限次数以无限接近1的概率？

单向功能的定义. 。 $ x in_r {0,1 }^n，y = f（x），pr [a（y）= x'st f（x'）= y] < epsilon（n）$

在这种情况下，使用可忽略的功能的用法非常直观，成功的概率是由可忽略的函数$ epsilon（n）$限制的。我不确定它与计算安全的加密方案的存在如何相关（当然，加密方案是可取的），但是，如果$ epsilon（n）$可以安全地忽略，而不是正常。

问题是我不太了解为什么我们需要可忽略的功能。通过提及很少的定义，我试图对我完全不了解的内容更具体。

如果有人能阐明使用微不足道的功能，我将不胜感激

Answer 1

如果您重复一份算法$ a $，而概率可忽略不计$ epsilon（n）$成功，则输入长度为$ n $的次数，直到第一次成功发生为止 几何分布 随机变量$ s $。 $ s $的预期值是

$$ mathbb {e}（s）= frac {1} { epsilon（n）} = n^{ omega（1）} quad。

因此，使用$ a $多项式多次（例如$ p（n）$）的攻击者不会具有成功的可能性，我们将通过比较预期值来看到。让$ a'$为算法，重复$ a $ p（n）$ times，随机变量代表$ a'$的次数，直到第一个成功应命名为$ s'$。然后：

$$ mathbb {e}（s） leq p（n） mathbb {e}（s'） quad，$$

因此，$ a'$的成功概率无可忽视，这意味着$ a $的概率不可忽略，因为两个多项式的产品再次是多项式。因此，允许可忽略的概率没有损害（至少对于多项式有限的对手）。

从本质上讲，这是一个间接证明，证明$ p（n） epsilon（n）$对于任何多项式$ p $仍然可以直接证明：$ p $由其最大的指数主导，因此n） in mathcal o（n^c）$ for Some $ c in Mathbb {n} $。另一方面，$ epsilon（n） in O（n^{ - d}）$ in mathbb {n} $ in o（n^{ - d}）$。定义$ d'= dc $，您将获得$ epsilon（n） in O（n^{ - （d'+c）}）$ in in mathbb {n} $。因此，$ p（n） epsilon（n） in O（n^{ - （d'+c）}） Mathcal o（n^c）= o（n^{ - d'}）$ for All $ d' in mathbb {n} $，这再次可以忽略不计。

如果您坚持使用$ 0 $（或$ frac {1} {2} $的概率，那么在区分方的情况下）许多应用程序变得（几乎）不可能。考虑一个加密哈希函数$ h $和一个未知参数$ x $。找到PreImage $ X'U $ ST $ H（X'）= H（X）$的概率占所有$ X $不能为$ 0 $，因为测试所有可能的输入最终将导致成功。但是，您可以选择使用$ 2^{ - n^{ omega（1）}} $限制概率或类似的概率，并仅调用这些函数可忽略不计。但是在大多数情况下，只考虑了无限的对手或有效的对手（即多项式界限）对手，因此不同的概念并不重要，因为有效的对手可以破坏任何东西，而无界的对手可以打破两者。