證明偽隨機函式的存在
作為我自己學習的一部分，我一直在閱讀 Katz 和 Lindell 的《現代密碼學簡介》一書，並且遇到了這個我不知道如何進行的練習。**練習是：（**練習 3.8）
無條件地證明一個有效的偽隨機函式的存在 $ F:{0,1}^* \times {0,1}^* \mapsto {0,1}^* $ 其中輸入長度是密鑰長度的對數（即， $ F(k,x) $ 僅當 $ |x| = log |k| $ ， 在這種情況下 $ |F(k,x)| = |k| $ ).
還有一個提示指出您應該使用任何隨機函式也是偽隨機的事實。
這是我最初的構想：
我們要求偽隨機函式與從映射的函式集中均勻隨機選擇的函式無法區分 $ log|k| $ 位串到 $ |k| $ 位字元串（假設這個集合被稱為 $ Func_{log,|k|, \mapsto |k|} $ ）。我猜我們需要計算這個集合中有多少個函式才能計算出選擇隨機函式的機率， $ f $ ，從這個集合。
我知道函式集 $ Func_{n \mapsto n} $ 映射 $ n $ 位串到 $ n $ 位串包含 $ 2^{n*2^n} $ 職能。但是我的第一個障礙是計算有多少函式 $ Func_{log,|k|, \mapsto |k|} $ 因為這個集合中的函式不像它們在 $ Func_{n \mapsto n} $ .
如果我可以計算這個值，那麼我將通過計算可能的偽隨機函式的數量來解決問題的其餘部分（顯然由 $ |k| $ 自從 $ k $ 是隨機均勻選擇的）。然後我希望，如果有類似數量的功能 $ Func_{log,|k|, \mapsto |k|} $ （雖然我推測還有更多 $ |k| $ 這個集合中的函式），然後最終嘗試證明任何 ppt 區分器都很難區分偽隨機函式和隨機選擇的函式。
我不知道這是否正確，我也不知道如何將提示帶入遊戲。我所能想到的就是證明它可能會更容易 $ F $ 與另一個也恰好是隨機選擇的偽隨機函式沒有區別。
如果有人可以提供有關如何計算函式數量的提示 $ Func_{log,|k|, \mapsto |k|} $ 或有關如何解決此問題的指示，那就太好了。正如我所說，我是為了自己的利益而做這些練習，所以我並不熱衷於立即獲得完整的解決方案。
儘管這是一個已有 4 年曆史的話題，但似乎以下內容應該有效：
我們可以構造一個函式 $ F_k(x) $ 帶輸出長度 $ l_{out}(n)=l_{key}(n)/2^{l_{in}(n)}=n/2^{O(\log n)} $ .
分鑰匙 $ k $ 進入 $ 2^{O(\log n)} $ 具有相等長度的塊，表示為 $ k_i $ 和 $ i=1,2,\dots, 2^{O(\log n)} $ . 因為 $ k $ 均勻分佈在 $ {0,1}^n $ , 也是 $ k_i $ .
$ F_k(x)= k_x $ 是偽隨機函式。
前言：當然，以下單獨的測試並不是無條件的測試。請參閱下面的說明。
有趣的文章亞歷克斯。斯坦福大學的 Dan Boneh 和 Coursera 課程 Cryptography I 和 II 討論了 PRG 的統計測試，這些測試與 PRF 的算法相關，如下所示：
$ {0,1}^n $ 位串使得 $ A(x) $ 在哪裡 $ x $ 是輸入字元串–輸出 $ 0 $ 或者 $ 1 $ . 在哪裡 $ 0 $ = 非隨機且 $ 1 $ =隨機。正如 Katz 所討論的那樣，PRF 與真正的隨機函式無法區分。
例子包括 $ A(x) = 1 $ 當且僅噹噹且僅當 $ 0 $ ’ 在給定的字元串中 $ x $ 和數量 $ 1 $ ’s 在字元串中 $ x $ 差別不大。# $ 0(x) $ - # $ 1<= 10 * \sqrt n $ .
這是 Boneh 的第二個例子： $ A(x) = 1 $ 如果連續 0 的數量是 $ 00x $ 和 $ n/4<= 10*\sqrt n $ . $ n/4 $ 僅代表均勻分佈的 25% 機會。
在 Boneh 的第三個範例中，我們現在可以看到日誌：
$ A(x) = 1 $ 當且僅當 max-run-of-0 $ (x) <= 10* log_2 (n) $
為了開始實際測試安全的 PRF/PRG，我們必須了解優勢的概念：
在哪裡 $ G:K–> [0,1]^n $ 是 PRG 和 A 統計檢驗 $ [0,1]^n $ 那麼我們可以定義以下內容：
進階 PRG
$$ A,G $$= 公關$$ A(G(k)) = 1 K<–R K - Pr [A(r) = 1 $$r<– R {0,1}^n 其中我們正在計算在種子空間內求和為 1 的特定機率，以及從生成器輸出的 ST 輸出和真正隨機字元串輸出 1 的可能性有多大。