歸納法在計算密碼學中存在問題 - 為什麼？
在 Lindell 博士的講座The Yao Construction and its Proof Of Security中，在簡要解釋混合論證時，他聲明數學歸納是計算密碼學中的一個問題。他解釋說混合論證“像”數學歸納法，但不一樣。
據我所知，數學歸納法和混合參數並不相同，因為對於混合參數，您需要一個有限的 ( $ k $ ) 證明工作的分佈序列（即，最終限制 $ k $ 最大差異可忽略不計* $ k $ ，可以忽略不計）。對於無限序列，這是行不通的。
有人知道林德爾博士是什麼意思嗎？我懷疑這是與可計算性相關的更深層次的問題，但我不確定。
謝謝！
歸納的問題是它通常隱藏的問題。我舉個例子。假設我想證明 $ n $ 樣品 $ X $ 難以區分 $ n $ 樣品 $ Y $ ，假設單個樣本無法區分。我沒有進行混合論證，而是通過歸納來證明。基本情況是直接的，因為假設無法區分單個樣本。接下來，我假設 $ i $ 並證明 $ i+1 $ . 在這個主張中，我證明對於每個 PPT 對手 $ \cal A_{i+1} $ 誰能分辨 $ i+1 $ 機率不可忽略的樣本，存在一個 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 那裡學到的。）