動機
一個概念類即使由可高效求值的函數組成,也可能無法被高效學習。求值時掌握秘密密鑰;學習時密鑰隱藏,學習器只能看到樣本。偽隨機函數形式化了一種特別強的差異:不知道密鑰時,即使算法能選擇多項式數量的輸入,也無法可靠地區分帶密鑰函數與均勻隨機函數。
如果高效 PAC 學習器能從隨機樣本預測這種族中的每個函數,其預測器在帶密鑰函數和隨機函數上的表現便會不同。這一差異可以轉化成預言機區分器。論證依賴明確的偽隨機函數假設:它既不證明無條件計算困難性,也不聲稱每個密碼構造都難以學習。
兩個計算模型
定義 10.1.1
(可高效計算的偽隨機函數族)
對每個安全參數 ,令 ,密鑰從 均勻選取,其中 為多項式。該族由確定性函數
組成,並由同一個算法在關於 的多項式時間內計算。預言機區分器 接收 ,可自適應地選擇輸入並查詢函數,最後輸出一個比特。若其包括預言機調用在內的運行時間關於 為多項式,則稱它為概率多項式時間區分器。
若對每個這樣的 ,以下兩個實驗中輸出一的概率之差的絕對值關於 可忽略,則稱該族偽隨機:
- 帶密鑰實驗:抽取一個均勻密鑰 ,每次查詢都使用同一個函數 回答。
- 隨機函數實驗:均勻抽取一個函數 ,每次查詢都使用同一個 回答。
非負函數 可忽略,指對每個正多項式 ,充分大的 均滿足 。在隨機函數實驗中,不同輸入處的值是獨立公平比特,但重複輸入會重複此前答案。等價地,可以只在某輸入第一次被查詢時賦予新的公平比特,並保存該值。
隨機函數是理想預言機,不是交給區分器的多項式大小表格。對於多項式次數的調用,可以按需生成並保存答案。不可區分性假設量化所有自適應區分器,其存取方式比隨機有標籤樣本更強。下文歸約只使用獨立均勻抽取的查詢點,所以僅對多項式個此類隨機查詢的安全性也已足以產生矛盾。每個實驗中密鑰或隨機函數只抽取一次,而非每次查詢重新抽取。
定義 10.1.2
(高效的無分布假設 PAC 學習)
令 。無分布假設 PAC 學習器接收 、精度和失敗參數 ,並能取得獨立有標籤樣本 ,其中 是 上任意分布,目標 。它輸出二元假設 ,滿足
「高效」要求對所有輸入及隨機選擇的最壞情況運行時間與請求樣本數關於 為多項式,並要求輸出表示能夠在多項式時間內求值。學習器不必輸出 中的成員:允許非恰當假設。
外層概率針對訓練數據和學習器隨機性,內層概率是所得假設的總體誤差。保證必須對每個目標和每個輸入分布成立。證明只使用均勻分布,所以實際上也排除了只需滿足這個固定均勻分布上保證的高效學習器;學習器可以知道該分布。
歸約定理
引理 10.1.3
(隨機函數的新點測試界)
令 均勻隨機。一個算法至多進行 次預言機查詢,查詢可自適應且允許重複,並根據記錄和隨機性產生可高效求值的二元預測器 。之後獨立均勻抽取 ,其預測與 一致的概率至多為
這是資訊界,去掉高效性要求仍成立。證明是對記錄取條件:未查詢處的隨機函數值仍是獨立公平比特,而 落在至多 個已查詢點的概率至多為 。
定理 10.1.4
(偽隨機性排除高效學習器)
假設上述二元函數族對每個概率多項式時間預言機區分器都是偽隨機的。則在上述模型中,不存在該 的高效無分布假設 PAC 學習器。事實上,即使學習器只需滿足均勻分布下的 PAC 保證、且允許輸出類外可高效求值的假設,這樣的學習器也不存在。
這是有條件的蘊含。它不聲稱只要密鑰隱藏,某個具體帶密鑰算法就偽隨機,也不無條件地建立所假設的函數族存在。
構造區分器
證明
(訓練後在獨立點測試)
假設這樣的學習器 存在。固定 後,其運行時間和樣本數在所有輸入及隨機選擇下都由某個多項式 控制。區分器 能存取未知預言機 ,它不是 就是 。
每當 請求一個有標籤樣本, 就獨立均勻抽取 ,查詢 並返回 。這些輸入獨立抽取,但可以重複。當 輸出可高效求值的假設 後,區分器再獨立均勻抽取一點 、查詢 ,並且僅在 時輸出一。整個模擬包括這個求值和預言機調用,都在概率多項式時間內完成。
在帶密鑰實驗中,先固定任意密鑰 。模擬數據是由 標記的獨立均勻樣本,所以 PAC 保證適用。所得假設以至少 的概率在均勻分布下具有至多 的誤差。給定這樣的假設,獨立測試點以至少 的概率被正確標記。因此
此下界對每個密鑰都成立,然後才對隨機密鑰取平均。未滿足 PAC 保證的訓練運行,其接受概率非負;無需額外假設。
在隨機函數實驗中,令 為訓練輸入中不同點的集合。給定訓練記錄和學習器隨機性後, 和 都固定。若 , 是新的獨立公平比特,條件匹配概率恰為 ;若 ,匹配概率可能達到一。因為 且 獨立均勻,
所以
區分器的優勢至少為 。因為 是多項式,充分大的 均滿足 ,因此優勢至少為 。一個最終始終不小於 的量不可忽略,這與偽隨機性矛盾,定理得證。
證明透視
碰撞項是歸約的一部分
真正的隨機函數會記住某個輸入處的答案。只有測試輸入未在訓練中出現時,測試標籤才是新的獨立公平比特。有限定義域上必須估計碰撞概率,比較才有效。帶密鑰情形使用 PAC 泛化;隨機函數情形使用新輸入處的獨立性;假設能高效求值則保證所得區分器是多項式時間的。
樣本數不必恰好為 。即使學習器根據此前樣本決定何時停止,其調用次數仍至多為此多項式上界,而測試點在訓練後才抽取。對完整記錄取條件概率得到相同估計。無需要求所有訓練輸入互異:重複訓練點只會使 變小。
例題
例題 10.1.5
(有限定義域上的優勢計算)
設 ,學習器至多請求 個樣本。歸約中隨機函數的接受概率至多為
帶密鑰實驗的接受概率至少為 ,因此差至少約為 。這些是界,不是精確接受概率。漸近矛盾使用的是對所有充分大 均成立的多項式 ,而非單一數值參數。
例題 10.1.6
(為甚麼同一個隨機函數必須記住答案)
在兩點定義域 上,設一個訓練輸入和一個獨立測試輸入都均勻抽取。預測器記住所觀察標籤:如果測試輸入重複便使用它,否則公平隨機猜測。測試發生碰撞的概率為 ,所以它與均勻隨機函數一致的概率為
若把每個測試標籤都稱為獨立公平比特,就會錯誤地得到 。一般界在此也給出 。當 增大而樣本數為多項式時,碰撞項趨零,但有限 時它並非恆為零。
例題 10.1.7
(歸約不要求假設屬於原類)
學習器可能輸出一個電路,它不等於任何密鑰 所對應的 。區分器仍可在 求該電路的值並與預言機比較。證明只使用 PAC 誤差保證及高效求值,從不要求恢復密鑰。因此矛盾不需要破解秘密密鑰;能預測新輸入便已足夠。
反例模式
密鑰隱藏本身不保證偽隨機性
令 ,其中 。該函數可高效計算且密鑰隱藏,但對每個密鑰都有 。區分器查詢一次 ,若答案為零便輸出一。在帶密鑰實驗中接受概率為一,在均勻隨機函數實驗中為 ,優勢為 。該函數族不滿足所述偽隨機性假設;該奇偶族也可從均勻有標籤樣本透過二元線性代數高效學習;這不與定理矛盾,因為該族不滿足偽隨機假設。秘密參數本身不是安全證明。
常見錯誤
常見錯誤
(對重複輸入把隨機函數換成獨立標籤)
隨機函數在此前未見過的輸入上給出獨立公平標籤,但對重複輸入不會如此。應考慮碰撞事件,或者有意從訓練集之外抽取測試點並分析分布變化。上面的證明保持測試點均勻,並明確計入碰撞項。
常見錯誤
(誇大有條件歸約的結論)
結論假設存在高效可計算且滿足預言機偽隨機性的函數族,並不無條件地證明這樣的族存在,也不保證某個具體實現安全。它還依賴學習器的輸出可高效求值:否則所構造的區分器未必在多項式時間內運行。
總結
若能在均勻分布下 PAC 預測每個帶密鑰函數,就可以用一個新的隨機測試輸入區分偽隨機函數與真正隨機函數。帶密鑰實驗中預測經常成功;隨機函數在未見過的點不可預測,有限定義域上的碰撞概率由顯式項控制。因此預言機偽隨機性在所述模型下有條件地排除高效學習,即使允許非恰當假設也如此。
練習
快速檢查
(在隨機函數實驗中,令 ,訓練樣本至多 個。用證明中的界估計單點測試接受的概率。)
使用界 。
解答 · 答案
證明給出 。實際值取決於學習器及訓練輸入是否重複;該表達式是上界。
快速檢查
(將歸約中的參數改為 、。給出帶密鑰實驗接受概率的下界,以及用 表示的區分優勢下界。)
把假設良好的概率乘以測試點被正確標記的概率。
解答 · 答案
帶密鑰接受概率至少為 ,隨機函數接受概率至多為 ,故優勢至少為 。若 是多項式,則充分大的 使該界為正且不可忽略。
快速檢查
(某模擬器對重複的預言機查詢每次都回答一個新的獨立公平比特。給出一個兩次查詢的區分器,說明這不是隨機函數實驗。)
隨機函數會記住它的答案。
解答 · 答案
對同一輸入查詢兩次;若兩次回答相同則輸出一。對同一個隨機函數,答案總相同;對每次重新生成的獨立公平比特,相同概率為 ,兩種接受概率之差為 。
快速檢查
(對帶密鑰奇偶族 ,計算零輸入區分器的一次查詢優勢,並解釋它違反了甚麼假設。)
在 處計算每個帶密鑰函數的值。
解答 · 答案
帶密鑰函數在 的答案恆為零,而隨機函數在該點的值是公平比特。答案為零時接受,得到接受概率一與 ,故優勢為 。此族對所允許的預言機區分器不偽隨機。