Barak et.al. "On the (Im)possibility of Obfuscating Programs" (CRYTPO2001)読み始め

Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, Yangと大所帯.
1-3章をざっと読んだ限りだと, Canetti, Goldreich, and Haleviの"Random Oracle Model v.s. Real World"みたいなノリだなぁ. あれは, うまいこと二項関係を作って, 中が覗けないオラクルだとその関係を満たすような二項の片側が求められないけど, 中が覗ける（自前で計算できる）関数だと作れるということをうまく使って, ROMで安全だがRealWorldではどうやっても安全性を保てないような署名・暗号を作っていた.
こっちは, オラクルから計算できないけど, プログラムからは計算出来るような, 性質を作れていしまうみたいな話になってる. なので, どうやっても難読化出来てないようなプログラムの関数族の分布がある, と. (確率が入ってくるのは, 難読化をPPMが行うから.)
Black-Box Model v.s. Non-Black-Box Modelは好物になりそうだ.
自分でやる気にはならないが, 見ている分には面白い. しばらくBarakの論文は追いかけよう.