mshkhのブックマーク - はてなブックマーク

ゲームと困難性 - 186 @ hatenablog
前置き CiNii - ぷよぷよはNP完全はてなブックマーク - CiNii - ぷよぷよはNP完全全て頭に一般化が付きます. 色々結果はありますが, 問題の定式化によって当然難しさが変わりますのでご注意を. 定義は元論文を見て確認してください. 2人ゲームオセロ PSPACE完全 (岩田, 笠井 1994) 将棋 EXPTIME完全 (安達, 亀川, 岩田 1987) 囲碁 EXPTIME完全チェッカー EXPTIME完全 (Robson 1984) チェス EXPTIME完全一般化しりとり PSPACE完全マスターマインド NP完全 (de Bondt 2004, Stuckman and Zhang 2005) 一般化アマゾン PSPACE完全 (清見, 宇野 2005) シャノンのスイッチングゲーム PSPACE完全 1人ゲーム一般化詰め将棋 EXPTIME完全 (横
mshkh 2008/08/10
ゲーム

計算量
リンク
Goh, Katz, Jarecki, and Wang (JoC, vol. 20, No. 4, 2007) - 186 @ hatenablog
E.-J. Goh, J. Katz, S. Jarecki, and N. Wang “Efficient Signature Schemes with Tight Security Reductions to the Diffie-Hellman Probl ems” (Journal of Crypto logy 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ビットの
mshkh 2008/04/16
署名

安全性

帰着

セキュリティ
リンク
Rosen and Segevの新しいの - 186 @ hatenablog
Crypto logy ePrint Archive: Report 2008/134 - A. Rosen and G. Segev “Efficient Lossy Trapdoor Functions based on the Composite Residuosity Assumption” Peikert and Waters (STOC '08, Crypto logy ePrint Archive: Report 2007/279)で新しく提唱されたプリミティブとしてLossy TDFがある. これは鍵生成の時にモードが2つある. Injectiveモードだと普通のTDFの記述 (公開鍵) が生成される. Lossyモードだと情報が失われるような関数の記述 (公開鍵モドキ) を生成する. (具体的には値域が平文空間より狭いという定義. 当然, 情報が失われる.) また, 公開鍵と
mshkh 2008/03/28
Lossy Trapdoor Functions

暗号
リンク
1