読者です 読者をやめる 読者になる 読者になる

ePrint

Cryptology ePrint Archive: Report 2008/441 - G. Leurent, P. Q. Nguyen “How Risky is the Random-Oracle Model?”
ROを現実のハッシュで実装するときに, RSAなんかと組み合わせた場合, ROの出力が1024ビットとか必要になってしまう. さて, どうやって160ビット出力のハッシュからそんな出力を作るのか. そこそこ考えられているが数は少ない.
Bellare, Rogaway'93なんかは, 原像が求められるとすると2^68回でダメ. Bellare, Rogaway '96だと,衝突が見つけられると2^{106}回でダメ. ってことはですねぇ, 誕生日攻撃にすら至ってないと.
Rabin系の話 (Rabin署名とBGH'07のIDベース暗号) だとROMでもハッシュの衝突が見つかると秘密鍵が漏れる可能性があることを指摘している. (具体的には, 1/2乗根のどれを取るかを指摘していないので漏れる.)
Rabin/Williams署名に変えても同様らしい.
付録AでGPV署名も扱っていて大体同じ内容.