ランダムオラクル
有限のステップ数から成るアルゴリズムで計算可能な関数では、真のランダムオラクルを実装することは出来ない(何故なら、定義により無限のステップ数が必要だからである)。
実際、ある種の電子署名や暗号方式は、ランダムオラクルモデルで安全性を証明されているが、ランダムオラクルを実在する関数に置き換えようとすると、どのような関数に置き換えても明らかに安全ではなくなることが知られている。それでもなお、その他の暗号方式に関しては、ランダムオラクルを仮定して暗号の安全性が証明されれば、その暗号方式が安全であるという非常に強い証拠となる。
一般に、ある暗号方式が安全であると証明されたなら、その暗号方式に対する攻撃は、証明された範囲外の性質を利用するか、または証明に用いられた何らかの仮定を覆す必要がある。例えば、暗号方式が素因数分解の困難性を利用しているのなら、この仮定を覆すには高速な素因数分解アルゴリズムを発見しなければならない。ランダムオラクルで言えば、これを覆すには、実際に適用されているハッシュ関数について何かしら未知の脆弱性を発見しなければならない。そのような脆弱性がありそうに無い良いハッシュ関数を前提にすれば、所与の暗号方式は安全だと考えて良いことになる。