ランダムオラクル

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ランダムオラクル: Random oracle)は、暗号理論における一種の神託機械(理論的ブラックボックス)であり、あらゆる問合せに値域に一様分布するような(真の)ランダムな応答を返すが、同じ問合せに対しては毎回同じ応答をするものである。言い換えれば、ランダムオラクルは全ての入力を値域内のランダムな出力にマッピングする関数である。

ランダムオラクルは、暗号理論における証明で使われる数学的抽象である。典型的な利用法としては、あらゆる既知の関数が証明に必要とされる数学的特性を提供しないときに使われる。このような証明によって安全であると保証されたシステムは「ランダムオラクルモデルにおいて安全」あるいは「ランダムオラクル仮定のもとで安全」と言われる。反対語は、「スタンダードモデルにおいて安全」あるいは「標準モデルにおいて安全」となる。実際、ランダムオラクルは強いランダム性を必要とするときに、暗号学的ハッシュ関数のモデルとして使われる。一般にそのような証明は、システムやプロトコルを攻撃するのにランダムオラクルの(現実にはあり得ない)特性を使わないと解読できないことを示すことで安全性を示す。あるいは、暗号を破るのに難しいと思われている数学問題を解かなければならないことを示す。ハッシュ関数が常にランダムオラクルの特性を持つことを要求されるわけではない。標準モデルでは、衝突耐性(無衝突性)があることを示すだけでも安全であることが証明できる(例えば、Cramer-Shoup cryptosystem)。

ランダムオラクルは計算複雑性理論において長年に渡って研究されてきた(例えば Bennett & Gill[1])。Fiat & Shamir (1986)[2]では、ランダムオラクルの主な応用(電子署名作成のプロトコルからの対話の除去)が示された。Impagliazzo & Rudich (1989)[3]は、ランダムオラクルの限界を示した(秘密鍵交換において、単にランダムオラクルがあるだけでは不十分である)。Bellare & Rogaway (1993)[4]は、暗号設計におけるランダムオラクルの利用を主張した。その定義によれば、ランダムオラクルは無限長のビット列を生成し、必要な長さでそれを切り出して利用する。セキュリティの安全性の証明に使われる場合、ランダムオラクルは暗号を守る側も破る側も使えるものとする。1つのランダムオラクルは、問合せの先頭に固定ビット列を追加することで複数のランダムオラクルとして扱える(例えば、"1|x" と "0|x" というように問合せの前に 1 か 0 を付けるようにすれば、2台のランダムオラクルとなる。同様に、"00|x"、"01|x"、"10|x"、"11|x" とすれば4台となる)。

実際の関数で真のランダムオラクルとなるものは存在しない。実際、ランダムオラクルモデルで安全であると証明されている電子署名や暗号方式があっても、ランダムオラクルを実際の関数に置き換えると安全ではなくなることがある[5]。それにもかかわらず、ランダムオラクル仮定において暗号の安全性が証明されれば、その中で使われているハッシュ関数が未知の不適切な特性を持っていることを発見されない限り解読できないという非常に強い証拠となる。多くの暗号方式がランダムオラクルモデルで安全性を証明されており、例えば OAEP(Optimal Asymmetric Ecryption Padding)や PSS (Probabilistic Signature Scheme)がある。

関連項目[編集]

脚注[編集]

  1. ^ Charles H. Bennett and John Gill: Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1. SIAM J. Computing 10(1): 96-113 (1981)
  2. ^ Amos Fiat and Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO 1986: pp. 186-194
  3. ^ Russell Impagliazzo and Steven Rudich: Limits on the Provable Consequences of One-Way Permutations STOC 1989: pp. 44-61
  4. ^ Mihir Bellare and Phillip Rogaway, Random Oracles are Practical: A Paradigm for Designing Efficient Protocols, ACM Conference on Computer and Communications Security 1993, pp. 62–73 (PS and PDF).
  5. ^ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 (PS and PDF).

外部リンク[編集]