PRF 和隨機預言機有什麼區別？
偽隨機函式和隨機預言機有什麼區別？
- 區別僅在於 PRF 和 Random Oracles 的域，前者俱有固定域，後者只要格式正確就可以作用於任何輸入？
- 擁有一個隨機預言機是一個更強的假設，這是為什麼呢？
$ \newcommand{\str}[1]{{0,1}^{#1}} $
粗略地說，偽隨機函式之於隨機預言機就像計算加密方案之於一次性密碼——前者是資訊論後者的計算模擬。
為簡單起見，讓我們將域和共同域固定為所有的集合 $ n $ 位字元串。讓我們考慮一下集合 $ \mathcal{F}_n $ 映射的所有功能 $ n $ 位到 $ n $ 位，即 $$ \mathcal{F}_n=\left{f:\str{n}\rightarrow\str{n}\right}. $$ 一個隨機的預言機 $ n $ bits 是一個從 $ \mathcal{F}_n $ 以oracle的形式呈現。也就是說，任何可以訪問隨機預言機的機器都可以（通過在其預言機磁帶上寫入）在輸入上查詢它，並將接收到函式的值作為回報（寫回預言機磁帶上）。請注意，由於有 $ |\mathcal{F}_n|=(2^n)^{2^n} $ 這樣的函式，一個特定的機率 $ f\in\mathcal{F} $ 被選為 $ 1/|\mathcal{F}_n| $ . 此外，由於它是隨機均勻選取的，隨機預言機是不可壓縮的，唯一明確表示它的方法是通過它的函式表（它的大小為 $ n2^n $ 位）。（這就是為什麼它被呈現為一個神諭。）
另一方面，偽隨機函式是對計算有界機器“出現”隨機的一系列函式。更正式地說，它是一組明確的、可高效計算的鍵控函式 $ n $ -位字元串 $$ \mathcal{G}n={g_k:\str{n}\rightarrow\str{n}}{k\in\str{n}} $$ 那是偽隨機的：對於任何計算有界的機器，有預言機的世界 $$ f(\cdot):f\leftarrow\mathcal{F}_n
(\text{random}) $$ 和 $$ g_k(\cdot):g_k\leftarrow\mathcal{G}_n\stackrel{\Delta}{=}k\leftarrow\str{n}(\text{real}) $$ 顯得難以區分。換句話說，它與計算有界機器的隨機預言沒有區別。注意 $ \mathcal{G}_n\subset\mathcal{F}_n $ 更重要的是，函式的數量 $ \mathcal{G}_n $ 比中的要小得多 $ \mathcal{F}_n $ :$$ |\mathcal{G}_n|=2^n\ll|\mathcal{F}_n|=(2^n)^{2^n} $$ 然而，由於偽隨機性，計算有界的機器不應該能夠分辨出這一點。使用偽隨機函式代替隨機函式的優點是它們具有簡潔的表示：一旦家庭 $ \mathcal{G}_n $ （我們需要明確且可有效計算）是固定的，函式由鍵表示 $ k $ 因此它的顯式表示很簡單 $ n $ 位長。
現在來回答問題
區別僅在於 PRF 和 Random Oracles 的域，前者俱有固定域，後者只要格式正確就可以作用於任何輸入？
不一定，人們通常談論一組PRF，即每個比特長度一個： $ {\mathcal{G}n}{n\in\mathbb{N}} $ .
擁有一個隨機預言機是一個更強的假設，這是為什麼呢？
這個問題可以用不同的方式來解釋。假設一個對象 $ B $ 據說比假設另一個物體更強大 $ A $ 如果 $ B $ 暗示 $ A $ （但另一個方向不成立或未知）。例如，DDH 是比 CDH 更強的假設，或者 IND-CCA 是比 IND-CPA 更強的假設。從這個意義上說，不可能直接將隨機預言機與 PRF 進行比較，因為前者生活在一個相對化的世界（即有預言機的世界）中，而後者則不需要。由於隨機預言的不可壓縮性，從隨機預言建構 PRF 不太可能被明確和簡潔地描述（正如@Ievgeni 指出的那樣）。另一方面，人們可以談論使用 PRF 模擬隨機預言機——但是，對於無界的對手來說，這似乎是可區分的。
也就是說，基於 PRF 的協議優於基於隨機預言機的協議，因為實際上我們不知道如何實例化隨機預言機。可以用 SHA3 之類的具體散列函式（即隨機預言方法）替換它，但該協議僅具有啟發式保證（此處和此處的討論），並且在某些情況下已知不安全（此處的討論）。然而，我們確實知道如何（明確地）從存在單向函式的溫和假設中構造偽隨機函式（在此處討論）。
- $ ;;; $ 不。 $ : $ PRF 涉及密鑰；隨機預言機沒有。
- $ ;;; $ 可以從隨機預言機建構 PRF。