Goh, Katz, Jarecki, and Wang (JoC, vol. 20, No. 4, 2007)

E.-J. Goh, J. Katz, S. Jarecki, and N. Wang “Efficient Signature Schemes with Tight Security Reductions to the Diffie-Hellman Problems” (Journal of Cryptology 20(4): 493-514, 2007)
Eurocrypt 2003のとACM CCS 2003のをあわせたものらしい. 何となく読んでみた.
DL系のPoKにFiat-Shamir変換を施して得られる署名だと証明中にPointcheval and SternのForking Lemmaを使うので帰着効率が悪い. BellareらのReset Lemmaでも同様. それを避けるためのテクニックを考案し, CDH仮定とDDH仮定から効率の良い署名を構成.
これまでにkビットの乱数を加えて帰着効率をよくする話があった. 実は1ビット加えるだけで半分のクエリに問題を埋め込める. 何とまぁ.

タメになった. Random Oracleを使わないので使用機会はあるまいと思ったが, 直近の論文で初めて使ったことを思い出した. そうねー, あれは元々ROでもタイトな帰着だから別に問題無いか. プリミティブが違うしな.

NY君の情報によりKoblitz and Menezes “Another look at “provable security” II&rduo; (INDOCRYPT 2006, Cryptology ePrint Archive: Report 2006/229を見た.
4章で帰着効率の話を行っている. 4.3節ではKatz and Wangの結果が挙げられている.
1ビット付けるだけで帰着効率が良くなるなんてねぇ? 1ビット付けるだけで現実の暗号系の安全性が上がるっておかしいだろう. とかそういう話をしている.
いや, そもそも証明がランダムオラクルモデルだから1ビット付けるだけで利くんだろ? だったら帰着効率の話の前にランダムオラクルモデルを疑うべきなんじゃないすかねぇ(;´Д｀)