Polynomially Secure Cryptography
- Polynomially secure crypto
- Michael Backes, Markus Duermuth, and Dominique Unruh
CRYPTO 2008 rump session より．要するに逆方向も多項式時間（だけど順方向よりもだいぶ時間がかかる）の一方向関数を仮定無しで構成しましょうというお話のようです（Work in Progress とあるのでまだやりかけの研究のようですが）．スライドを見ると，証明は以下のような方針に沿っているようです．
- HerBPTIME に対する階層定理で，難しい問題を得る．
- Uniform Direct Product Lemma で hardness amplification を行う．
- Merkle's Puzzle を使って鍵交換プロトコルを構成する．
- 鍵交換プロトコルから一方向関数を得る．
この方針についていくつか疑問点が残ります．まず１について，確率計算モデル（より一般的には semantic な計算モデル）の階層定理は Barak, Fortnow, van Melkeveek その他の研究者が研究していますが，アドバイス付きではないと今のところ階層定理は示せないはずです．このアドバイスの処理はどうするのかという点がまず引っかかります．
また，階層定理を使った場合に順方向計算の効率性の保証はどうするのでしょうか．階層定理で言えるのは，ある言語が例えば n^10 時間では解けないが，n^12 時間では解ける，という感じの結果なので，計算できる方向はどうしてもできない方向よりも計算量が必要に思えます．Merkle's Puzzle のパズルの数を増やして敵対者の計算時間を稼ぐかなとも思いましたが，結局，Impagliazzo-Luby の議論から一方向関数を得ようとしたときに確かプロトコルの実行時間が順方向に効いてきたはずなので，それでも上手くいかない気がします．
結果は非常に面白く，自分でも証明を試みてみようと思うのですが，スライドによると proof sketch だけで 20 ページあるとか．
