一般ハードコア関数の証明とフーリエ変換

8月5日はハーコーということでハードコアの日だそうです. (ちゃんと日本記念日協会に届け出たそうで.)

ということなのでハードコア関数の話をします.
Goldreich-Levinハードコア述語とリスト復号の話はよく出るんですが, GLハードコア述語とフーリエ変換の話はあんまり出ないんで大雑把な話を一席.

以下では, F=F2nとします.

述語bが関数f:F→Fのハードコア述語であるとは,

  1. b:F→{0,1}が多項式時間で計算可能,
  2. 任意の多項式時間の敵Dに対して, 無視できる関数εが存在し, \Pr_{x, D}[D(f(x))=b(x)] \leq \frac{1}{2}+\epsilon

が成立することです.

GoldreichとLevinいわく, 適当な一方向性関数f:F→Fに対して, f'(x,r)=(f(x),r):F×F→F×Fも一方向であり, b(x,r)=Σixiri mod 2はf'のハードコア関数である.

このハードコア関数の証明は以下の手順を踏みます.

  1. ハードコア性を破る敵Dを用いて, 一方向性を破る敵Aを構成する.
  2. とりあえずxとDに与える乱数を固定する.
  3. 標準的な議論から, F×coinsの部分集合Sが存在して,
    1. Sの割合はε/2以上
    2. Sに入るxとDのコインωの組に対して\Pr_{r \in F}[D(f(x),r;\omega)=b(x,r)] \geq \frac{1+\epsilon}{2}.
  4. xとωを固定して, xを求められることを示せば十分.

というわけで手元に
\Pr_{r \in F}[D_x(r)=b(x,r)] \geq \frac{1+\epsilon}{2}
を満たす決定性の敵Dxが存在するとしましょう.

rが入っている集合Fを2つに分割します.

  • Gd = {r | Dx(r)=h(x,r)},
  • Bd = {r | Dx(r)≠h(x,r)}

とします.
簡単な計算で, |Gd| = (1+ε) 2n-1, |Bd| = (1-ε) 2n-1であることが分かります.

こっから強自己訂正器に持っていくのがRackoff流の証明ですが, ここで視点を変えます.
今考えているb(x,r)をちょっと変更して, b'(x,r)=(-1)b(x,r)としましょう.
すると,
\Pr_{r \in F}[D_x=b'(x,r)] \geq \frac{1+\epsilon}{2}
を満たすDが存在すると考えてもいいわけです.

ここまでが前提です.
次にちょっと横道にそれてフーリエ変換の話を始めます.

F=F2nの離散フーリエ変換

関数fを要素としてもつ環V={f:F→R}を考えます. 和と積は項別に計算することにして演算を入れてあります.
この環に内積\langle f, g \rangle = E_{r \leftarrow F}[f(r) g(r)] = \frac{1}{2^n} \sum_{r \in F} f(r) g(r)という定義で入れます.
関数のノルムは内積の2乗ということにします.
するとf:F→{-1,+1}はノルムが必ず1になります.

次にフーリエ基底を用意します.
関数族{χx}x∈Fただし, \chi_{x}(r) = (-1)^{\sum_{i=1}^{n} x_i r_i} = (-1)^{b(x,r)} = b'(x,r)です.
定義より, χxのノルムは1です.
簡単な計算により, 任意のx≠x'で<χx, χx'>=0が言えます.
従って, この関数族はベクトル空間Vの正規直交基底になっています.

内積やノルムを入れた御利益として以下があります.

  1. g'(x) = <g, χx>と定義します. (gのフーリエ係数.)
  2. g(r) = Σx g'(x) χx(r)が成立します.
  3. ||g||2 = Σx g'2(x) = 1です.

合流

さて, 先ほど見たように, 今
\Pr_{r \in F}[D_x(r)=b'(x,r)] \geq \frac{1+\epsilon}{2}
を満たすDxが存在すると考えています.
面倒なので, g(r)=Dx(r)と置いて, b'(x,r)=χx(r)に注意すると,
\Pr_{r \in F}[g(r)=\chi_x(r)] \geq \frac{1+\epsilon}{2}.
書き直すと,
\Pr_{r \in F}[g(r) \chi_x(r) = 1] \geq \frac{1+\epsilon}{2}.
従って,
g'(x) = \langle g(r), \chi_x(r) \rangle \geq \epsilonが成立することになります.

以上より, xを求める問題だったのが, g(r)=D(f(x),r)の大きなフーリエ係数を求める問題に変わりました.
ありがたいことに, そのようなフーリエ係数の個数は高々1/ε2個しか無いこともノルムの議論から証明出来ます.
ここから先は頑張ってKushilevitz and Mansourなり, Akavia, Goldwasser, and Safraを読んでください. 以上.