Random oracle
暗号において、ランダムなオラクルは理論的なブラックボックス）であり、出力ドメインから（[一様分布] |一様に）[（ランダムに）]応答を選択して、照会が繰り返される場合、照会が提出されるたびに同じ方法で応答します。
別の言い方をすれば、ランダムオラクルはランダムに一様に選択された、すなわち、可能な各クエリをその出力ドメインからの（固定）ランダム応答にマッピングする関数である。
数学的抽象としての無作為なoraclesは1993年の[Mihir Bellare]と[Phillip Rogaway]（1993）の1993年出版の厳格な暗号の証明に最初に使われました。それらは、通常、メソッドの暗号ハッシュ関数が証明によって必要とされる数学的性質を持つことが証明できないときに使用されます。すべてのハッシュ関数がランダムなオラクルに置き換えられたときに安全であることが証明されているシステムは、[[標準モデル（暗号化）]標準モデルで保証されているのとは対照的に、ランダムなオラクルモデルでは安全です暗号]]。
アプリケーション[編集]
ランダムなoraclesが典型的に使用される<！ - talkページ "Weasel Words"を参照 - ＆gt;ハッシュ関数の出力に強いランダム性の仮定が必要なスキームにおける暗号ハッシュ関数の理想置換のようなものです。そのような証明は、攻撃者がオラクルから不可能な行動を要求しなければならないことを示すことによってシステムまたはプロトコルが安全であることを一般的に示しているか、それを壊すために[[ハード数学的問題|ハード]のリスト]と考えられる数学的問題を解決する。
暗号ハッシュ関数のすべての用途がランダムなoraclesを必要とするわけではない：[[Standard model（cryptography）|標準モデル]の定義を持つプロパティ（例えば、[衝突耐性]、[[preimage resistance （[Cramer-Shoup cryptosystem]）などの標準モデルでは、しばしば安全であることが証明されています。
RSA-FDHなど、ランダムオラクルモデルでは、多くのスキームが安全であることが証明されています（[最適な非対称暗号化パディング]とProbabilistic Signature Schemeがあります。 1986年に、[Amos Fiat]と[Adi Shamir]は、シグネチャの作成のためのプロトコルからの相互作用の除去という、ランダムなoraclesの主なアプリケーションを示しました。
1989年、Russell ImpagliazzoとSteven Rudichはランダムなoraclesの制限を示しました。つまり、それらの存在だけでは秘密鍵交換には不十分です。
1993年には[Mihir Bellare]とPhillip Rogawayしかし、自然なプロトコルのためにランダムなオラクルモデルのセキュリティの証拠は、プロトコルの "実用的な"セキュリティの非常に強い証拠を提供します。
一般に、プロトコルが安全であることが証明されている場合、そのプロトコルに対する攻撃は、証明されたものの外にあるか、または証明の前提条件の1つを破る必要があります。例えば、証明が整数分解の硬さに依存する場合、この仮定を破るために、高速整数分解アルゴリズムを発見しなければならない。むしろ、ランダムなオラクルの仮定を破るためには、実際のハッシュ関数の未知で望ましくない特性を発見しなければならない。そのようなプロパティが存在しないと考えられる良好なハッシュ関数については、考慮されるプロトコルは安全であると考えることができる。
ランダムなOracle仮説[編集]
Baker-Gill-Solovayの定理によれば、P supA＆lt; sup＆gt;となるようなオラクルAが存在することが示されたが、ベネット（Bennett）およびギル（Gill）によるその後の研究は、「{0,1} <n> から{0 、1}とすると、各入力要素は、他のすべての入力のマッピングとは無関係に、確率1/2で0または1のそれぞれに写像するようになる）、P B B NPB B B </ sup>同様の分離と、ランダムなoraclesが確率0または1でクラスを分離するという事実（[Kolmogorovのゼロ1法則]の結果として）は、ランダムなOracleの作成につながった2つの「許容される」複雑度クラスC 1 sub1は、 C 2＆apos;＆lt; 2＆apos;それらがランダムなオラクルの下で（確率1で）等しい場合にのみ等しくなる（複雑さのクラスの許容度は、BGPAにおいてIP_A PS A / 確率1のランダムオラクルA。
==理想的な暗号==＆lt;！--- User：StrewはセクションへのRの可能性をチェックしましたが、これは検索ではわからず、他の暗号を意味する可能性があります - ＆gt;
理想的な暗号は理想化されたブロック暗号をモデル化するために使われるランダムな順列オラクルです。 ランダム置換は、各暗号文ブロックを1つの唯一の平文ブロックに、またはその逆に復号するので、1対1対応があります。 いくつかの暗号証明は、すべてのプレイヤーが利用できる「順方向」置換だけでなく、「逆」置換も可能にします。
最近の研究では、10ラウンドまたは8ラウンドの[Feistelネットワーク]を使って、ランダムなオラクルから理想的な暗号を構築できることが示されました。
