ランダムオラクルモデルについて

おはこんばんにちは．

最近なぜか忙しいことが多くそのせいで睡眠時間とお金が飛んでいく大学生です．

そのせいか最近研究についても若干(そう思いたいだけ)進捗が伸び悩んでいますが，その数少ない進捗のなかでもう忘れかけていたのでランダムオラクルについて覚書をしておこうと思いますん．

ランダムオラクルは理想的なハッシュ関数として知られており，ある入力に対して一様分布のなかからランダムに出力しているアルゴリズムである．

同じ入力には同じ出力を出し，どのような入力も一定の長さのハッシュ値を返すところが大きなメリットである．

細かく言うとRSA暗号の(pq,公開鍵e,秘密鍵d),メッセージm,H(m)を出力と同時にそれの署名σ=H(m)^d mod pqと検査σ^e=H(m) mod pqが成り立つことを確認している．

これを攻撃する場合，攻撃者はハッシュ値とメッセージ,秘密鍵が分からないのでσの代わりにランダムに選んだrを対応表に書いていって攻撃可能にするが，そもそもmod に使われるp,qが大きい数の素数であり，どんな数になるかわからない，さらに3つの対応だけでもかなりの数になるので攻撃は無理であるということになっている．

一般的にハッシュ関数は不可逆の関数として知られ，偶然出力が一致しない限り暗号的には安全である．

この安全性は衝突性(長い入力も一定の長さの出力に縮めるため，どうしても入力が違うのに出力が同じになってしまうこと)をできるだけなくすことが鍵となってくるため，既に破られてしまったハッシュ関数もある．

間違ってもランダムオラクル作れないかなとかは思わないように．そんなに簡単にできてしまったら安全性もくそもないからである．

論文やプログラムのコメントでランダムオラクルをモデルとしている等あったらハッシュ関数を使っているんだなと思うように．

(今回自分が読む論文ではセキュリティパラメータの設定が書いてなかったので泣いています)

今回は時間がないのでこれでおわりんぬ．．．