问归纳在计算密码学中是有问题的--为什么？

EN

归纳的问题是它通常隐藏的东西。我举个例子。假设我想证明n X样本与Y的n样本是不可区分的，假设单个样本是不可区分的。我没有做混合论证，而是通过归纳来证明。基本情况是即时的，因为假设无法区分单个样本。接下来，我假设是i，证明是i+1。在此声明中，我证明了对于每一个能够以不可忽略的概率区分i+1样本的PPT对手D7，都存在一个PPT对手\cal A_i，它能够以不可忽略的概率区分i样本(或者是一个区分单个样本的区分者，但让我们暂时保留这一点)。这似乎足以证明这一点。

但是，如果\cal A_i运行的时间是\cal A_{i+1}的两倍(这当然很好，因为它们都是多项式时间)，会发生什么？然后，当我“放松”归纳，我将得到以下信息。假设存在一个概率多项式时间对手\cal A_n，它以不可忽略的概率区分n样本；让p(n)作为它的运行时间。然后，通过反复应用归纳论点，我得到了存在一个敌手\cal A_1，它区分单个样本，但在时间上运行2^n\cdot p(n)，因此没有任何矛盾。

另一个可能发生的问题如下。假设我们对归纳步骤的证明是这样的，即\cal A_{i+1}与不可忽略的概率\epsilon(n)相区别，因此\cal A_i与不可忽略的概率\epsilon(n)/2有区别。当然，这是好的，因为这两种可能性仍然是不可忽略的。然而，当我们展开归纳法时，如果\cal A_n与不可忽略的概率\epsilon相区别，则\cal A_1与概率\epsilon/2^n的区别是可以忽略的。因此，没有实现任何矛盾。

为了克服这一问题，可以在归纳步骤中明确证明\cal A_{i+1}和\cal A_i之间的运行时差是相加的，这意味着只存在一个附加的多项式因子。然后，在n (或任何多项式)的归纳步骤上，总的额外运行时间仍然是多项式。同样，如果区分概率有所降低，那么最终的结果仍然是不可忽略的。

我曾在一篇论文中使用过一次归纳，请参阅http://u.cs.biu.ac.il/~lindell/PAPERS/session-key.ps的22-23页，因此可以这样做。但我们必须小心。

(注:我从Oded Goldreich中学到的所有这些。)