究竟什麼才是隨機預言機（random oracle）呢？

01-25

維基百科：在密碼學裡面，隨機預言是一個預言（簡單說像是理論的黑箱），對任何輸入都回傳一個真正均勻隨機的輸出（請參考離散型均勻分布），不過對相同的輸入，該預言每次都會回傳一模一樣的輸出。換句話說，隨機預言是一個將所有可能輸入與輸出作隨機映射的函數。可是既然說對於輸入給出是隨機輸出，那又為什麼會是對相同的輸入，該預言每次都會回傳一模一樣的輸出呢？

@玄星和 @Goliath Li 已經介紹了 RO 的定義，我就不多重複。這裡重點說說 RO 的用處。

Random Oracle 是密碼學中 (Keyed) Pseudorandom Function，縮寫 PRF，的抽象。PRF 是一個函數 $f:K imes X o Y$ ，其中 Key Space K 一般取 ${0,1}^k$ ，X,Y 可以相同可以不同，不妨令 $X={0,1}^n, Y={0,1}^m$ 。f 是 PRF 當且僅當對於隨機選取的 key k， $f_k$ 和隨機選取的函數 $p:X o Y$ 在 Oracle access 下 Computationally indistinguishable.

應該可以注意到 PRF 和 RO 的驚人相似性。如果不知道 k，且只能詢問 $f_k(x)$ 的值。那 PRF 和 RO 是（Computationally）一樣的。這時攻擊者幾乎無能為力，因為在不同輸入下的輸出是 i.i.d. uniform，攻擊者不可能從中找到任何機會。攻擊者不可能做到的事情包括：預測下一個輸出，求逆，尋找碰撞 etc

但是問題來了：如果只能 Oracle access，就意味著每次想知道 PRF 在某個輸入下的值 $f_k(x)$ ，都要詢問一次。這樣的系統幾乎不可能是實用的。實用體系需要每一方都可以自行計算 PRF。因此 PRF 的某一部分，總是要暴露給攻擊者的。

密碼學界對此的回應。。。。。暫時把問題掃的地毯下面。。。假設有某種神奇的方式，可以允許攻擊者自行計算 PRF，又不給於其任何其它的幫助。

一種想法是把 PRF 包裝起來，比如用 Obfuscation，將計算 PRF 的程序混淆後再發給潛在的攻擊者。如果 Virtual Black Box (VBB) Obfuscation 可以實現，那這個問題就解決了，PRF 都可以用 RO 來 model。但現實往往是殘酷的 T_T。VBB、RO 等已經被證明是無法實現的 [這裡應該有點引用]。

比如一個簡單的「例子」，只用來建立直覺。假設我收到了一個被 VBB Obfuscate 的 PRF，看看有什麼事情我在 RO 模型下不能做但現在能做的。在 RO 模型下，我無法簡潔的描述這個函數，因為在我看來這個函數和隨機差不多（Computationally indistinguishable），而隨機函數需要指數長度的描述。但我拿到了 VBB Obfuscated PRF circuit 之後，這就是一個簡潔描述呀！Done.

當然能做這種程度的事情還不很厲害，人家原 paper 還有做更厲害的事情。

由於這個問題，大家對 RO model 的熱情其實有限。同樣遭遇的還有 RP (Random Permutation) model。如果證明使用了這些模型，會被認為提供了一些洞察/證據，但不夠 solid。

[這裡應該有點引用] 聽 Amit 說的，所以沒有引用。好在評論區里有人 @唐恬心補充了工作。

首先吐個槽：

英文維基這個詞條明明是給了隨機預言機(random oracle，簡稱RO)兩個大大不同的理解，偏偏只用了一個「Stated differently」（換句話說），而且中文維基還有翻譯問題.

當然，兩個理解都是正確的，下面我來解釋。

理解一

在密碼學裡面，隨機預言是一個預言（簡單說像是理論的黑箱），對任何輸入都回傳一個真正均勻隨機的輸出（請參考離散型均勻分布），不過對相同的輸入，該預言每次都會回傳一模一樣的輸出。

Random oracle

In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated it responds the same way every time that query is submitted.

對比中英文下劃線部分，應該發現問題了吧。「repeated」是指「重複出現的」，而不是「相同的」。

這種理解，其實代表下面這個通過與訪問者互動來確定RO狀態的過程。（interactive process）

符號O(x)指RO對於輸入x的輸出， L代表O(x)的長度。（L是安全參數n的函數）

1. RO一開始維護一張空表，表有兩列，一列是輸入，一列是輸出

2. 如果訪問者第一次的輸入為x, 則RO均勻隨機從 ${0,1}^L$ 中選一個值O(x), 把x記錄在表裡。

3. 對於第二個以及之後的訪問y，如果y沒有在輸入這一列出現，則RO均勻隨機從 ${0,1}^L$ 選出O(y), 反之，即y出現過，則把輸出這一列中，y對應的O(y)再次輸出。

這也就是「真正均勻隨機」和「對重複值輸出相同」的意思。

理解二

換句話說，隨機預言是一個將所有可能輸入與輸出作隨機映射的函數
Stated differently, a random oracle is a random mathematical function, that is, a function mapping each possible query to a (fixed) random response from its output domain.

翻譯又把(fixed)給扔了，這個至關重要。

此理解是說，在訪問者發起第一個問題前，RO的狀態就是以某種方式確定的了。

這個某種方式就是指，從所有的輸入範圍為所有01字元串，輸出長度為L的函數集合中，均勻隨機的選定一個函數F，作為此次RO的狀態。隨後，以F的方式來回應訪問者。L是安全參數n的函數。

看看Ran Canetti, Oded Goldreich, Shai Halevi三位大家在The Random Oracle Methodology, Revisited這篇論文里對RO的描述吧，就是上述的理解

http://eprint.iacr.org/1998/011.pdf

It is postulated that all oracle queries, regardless of the identity of the party making
them, are answered by a single function, denoted O, that is uniformly selected among all possible functions. The set of possible functions is determined by a length function $L_{out}(cdot),$ and by the security parameter of the system.

題外話，一個RO通常被當作安全的Hash函數，但通常只能在一次證明中使用，就是說，你不能拿著已經確定狀態、並且已知部分輸入輸出關係的RO放入另一個證明裡。新證明最好用「空白」的RO。

題主應該先去理解一下oracle是什麼吧

在計算機理論裡面經常可以看到oracle，這個oracle可以是一個程序一片代碼一個演算法一個機器也可以是一個函數甚至是一個關係。但我們只能知道這個oracle能做什麼，不清楚他是怎麼做的。所以經常講其稱為黑箱。

推廣一點，只要是對給定輸入做出輸出的東西都可以稱為oracle，人也是如此。那麼如果有一個非常混沌善變的人，那就可以把他抓起來做為一個random oracle。每次想隨機點什麼東西的時候，就去問他吧。

Random Oracle可以定義為輸入映射到輸出的任意一個函數，這個函數對Oracle本身是確定的，但對於查詢者來說不能得到這個函數的任何信息（除了他查詢過的輸入），所以每一次不同的查詢對查詢者來說都是隨機的。

因為預言機實際上起到的是一個黑匣子的作用，中間是存在一個固定的演算法的，這個演算法相當複雜且是保密的，因此相同的輸入值在經過了這個演算法的運算之後輸出的是相同的輸出值，就像數學上一個確定的函數，相同的數值代入運算幾次都會得到同樣的結果一樣。預言機存在的目的是為了讓你無法知道自己的輸入能得到什麼樣的結果，如果你給出兩個輸入，預言機同時給定兩個輸出的話，你不會知道這兩個輸出分別對應的是哪個輸入。