Cube Attack

Cryptology ePrint Archive: Report 2008/385 - I. Dinur, A. Shamir “Cube Attacks on Tweakable Black Box Polynomials”
Schneier先生が御執心のアレ. 流し読みした限りでは, ブラックボックスになっているF_2上のn変数d次多項式をいかにして求めるかという話であった. 適当な事前計算を済ませておくと, O(2^{d-1} n + n^2)回の演算で求まるとかなんとか.
攻撃者が設定できる変数がk (＞d-1) 個ある. d-1次元の超立方体の頂点ベクトルを考えてそこで多項式を評価して全部足すと, 次数が減った多項式を求める問題に帰着されるので良いらしい.
んだが, なんか納得いかないなぁ. 時間が出来たらまた読む.