RSA仮定または双線形写像付きCDH仮定の下, 標準モデルで安全な署名

Cryptology ePrint Archive 2009/028 - Susan Hohenberger and Brent Waters “Realizing Hash-and-Sign Signatures under Standard Assumptions.”
EUROCRYPT 2009に出るらしい. ポイントは署名者を状態付きにしていること (今, i番目の署名をつけたので次はi+1とか覚えておく.). 状態i, 正確にはiのビット数にも署名みたいなものを付けることで不思議とsRSAまで持っていかなくてもなんとかなっている. RSA仮定から作る方だけざっと読んだが詳しいところまで理解できてないので後でちゃんと読む. (Cramer-Shoup, GHRも読み直さんとなぁ.)
正確にはPRFとカメレオンハッシュが要るが, 両方とも上の仮定から作れるのでOK.

何か不思議ですよね. 未解決問題のところで, 格子仮定や一般の仮定からも作れるのか? という話が出ていたので格子業界の人は頑張りましょう.