Provable-Security
統一與不統一的PPT
我試圖了解 PPT，特別是統一和非統一 PPT 的區別。首先，這是我的看法：
機率多項式時間( PPT) 算法 $ A $ 是一種在多項式時間內執行的算法，但也可以訪問一些提供真正隨機位的預言。所以如果我們輸入 $ x $ 進入 $ A $ , 而不是得到輸出 $ y = A(x) $ 這是一個確定的值，我們得到一個隨機變數 $ Y $ 它有一定的機率是一組不同的值。
不統一的PPT $ A $ 是 PPT，其描述大小（即， $ |A| $ ) 不是常數，而是隨其輸入呈多項式遞增。我見過像這樣的定義 $ A = {A_1, A_2, \dots} $ 哪裡每 $ A_i $ 是一個PPT。
- 我的觀察/結論是錯誤的嗎？如果是這樣，請糾正我。
- 我看到的一些關於非統一 PPT 的定義是我們在輸入的同時插入一些“建議字元串” $ A $ . 但是那個建議字元串到底是什麼？
最好的祝福
你的觀察基本正確。非正式地如下：對於一個統一的 PPT 算法，考慮一個固定的圖靈機，它可以訪問一些隨機磁帶，算法的輸出是一個隨機變數。對於非均勻算法，最好考慮由輸入長度索引的一系列電路（因此對於每個輸入長度，算法可能表現出完全不同的行為）。但是您也可能將非均勻算法視為一種統一算法，它採用額外的與輸入長度相關的“建議字元串”，幫助算法解決該大小的問題（要使非均勻算法統一，只需始終傳遞空字元串）。
對於正式的定義，只需查看您心愛的複雜性理論書。談到加密，最近有一些關於這兩種模型的討論（通常簡化證明在統一模型中）。您可以查看Menezes (non-uniformity) 的頁面並跟進討論。