## 定義 ランダムオラクルモデルは、暗号プリミティブの安全性を論じるための説明装置(セキュリティモデル)の 1 つで、完全秘匿性・具体的安全性・識別不可能性(標準モデル)に続く第 4 のモデルとして位置づけられる。標準モデルほど一般的な保証を与えないが、より効率的な構成を導くことができる。中心となる思考実験は「箱の中の妖精(elf)」で、入力を受け取ると巻物(scroll)を見て過去に同じ問い合わせがあったかを確認し、無ければサイコロで乱数を生成して答え、記録を残す、というものだ。暗号プリミティブの実体はゲート配列やソフトウェアのアルゴリズムだが、その出力が統計的検定で「乱数と区別できない」なら、そのプリミティブは対応する型のランダムオラクルとして扱ってよい、というのがモデルの主張である。ランダムオラクルには少なくとも 4 つの型があり、それぞれ暗号プリミティブに対応する。(1) ランダム関数(任意長入力・固定長出力)= ハッシュ関数、(2) ランダムジェネレータ(短い入力・長い出力)= ストリーム暗号、(3) ランダム順列(可逆・固定長入出力)= ブロック暗号、(4) トラップドア一方向置換(公開鍵では計算できるが秘密鍵がなければ逆変換できない)= 公開鍵暗号。デジタル署名は、ランダム関数(ハッシュ)とランダム順列(署名者だけが一方向に計算できるブロック暗号)を組み合わせたものとしてモデル化される。(Source: [[@2020__Wiley__Security Engineering 3e - Chapter 5 Cryptography]], ch.5 §5.3〜§5.3.5) ランダム関数(ハッシュ関数)としてのランダムオラクルは、一方向性・第二原像計算困難性・衝突耐性という 3 つの性質を導く。とりわけ衝突耐性は誕生日定理(birthday theorem)と直結しており、出力が n ビットのハッシュ関数は約 2^(n/2) 回のハッシュ計算で衝突が見つかると期待される。この事実は、デジタル署名で使うハッシュ関数の出力長を決めるだけでなく、生体認証システムの誤同定確率(利用者数が数千人規模になると誕生日効果で衝突が起きうる)や、ストリーム暗号・ブロック暗号の利用モードの周期(2^(n/2) ブロックで反復が始まる)にまで及ぶ、セキュリティ工学で繰り返し現れる中心的な数学的事実である。(Source: [[@2020__Wiley__Security Engineering 3e - Chapter 5 Cryptography]], ch.5 §5.3.1, §5.3.1.1, §5.3.1.2) ## 横断的知見 - (このconceptは本 ingest が最初のソースであるため、複数ソースの突き合わせによる横断的知見はまだ無い。他章・他ソースがランダムオラクルモデルに触れた際に、ここへ積み増す。) ## 未解決の問い - ランダムオラクルモデルで安全性が証明されたスキームが、現実のハッシュ関数に置き換えたときに安全性を失う「ランダムオラクル分離」の具体例(Canetti-Goldreich-Halevi 型の反例)は、本書のどの章で扱われるか。第 20 章(Advanced Cryptographic Engineering)が実装レベルの応用を扱うため、そこでの言及を確認する必要がある。 - 標準モデル(識別不可能性・意味論的安全性)とランダムオラクルモデルのどちらで安全性証明を与えるかは、実務上どのような基準で選ばれているか。本章は概念の紹介にとどまり、選択基準までは踏み込んでいない。 ## 関連 - [[@2020__Wiley__Security Engineering 3e - Chapter 5 Cryptography]] — ランダムオラクルモデルの導入と、ハッシュ関数・ストリーム暗号・ブロック暗号・公開鍵暗号・デジタル署名への対応付け - [[ブロック暗号設計原則]] — ランダム順列としてのブロック暗号の具体的な内部構造 - [[暗号利用モード]] — ランダム関数・ランダム順列を実際のメッセージ処理に拡張する際の構成 - [[公開鍵暗号方式]] — トラップドア一方向置換の具体的な数学的実現 ## 出典 - Ross Anderson, *Security Engineering: A Guide to Building Dependable Distributed Systems*, 3rd Edition, John Wiley & Sons, 2020, Chapter 5, §5.3.