一般ハードコア関数の証明とフーリエ変換
8月5日はハーコーということでハードコアの日だそうです. (ちゃんと日本記念日協会に届け出たそうで.)
ということなのでハードコア関数の話をします.
Goldreich-Levinハードコア述語とリスト復号の話はよく出るんですが, GLハードコア述語とフーリエ変換の話はあんまり出ないんで大雑把な話を一席.
以下では, F=F2nとします.
述語bが関数f:F→Fのハードコア述語であるとは,
が成立することです.
GoldreichとLevinいわく, 適当な一方向性関数f:F→Fに対して, f'(x,r)=(f(x),r):F×F→F×Fも一方向であり, b(x,r)=Σixiri mod 2はf'のハードコア関数である.
このハードコア関数の証明は以下の手順を踏みます.
- ハードコア性を破る敵Dを用いて, 一方向性を破る敵Aを構成する.
- とりあえずxとDに与える乱数を固定する.
- 標準的な議論から, F×coinsの部分集合Sが存在して,
- Sの割合はε/2以上
- Sに入るxとDのコインωの組に対して.
- xとωを固定して, xを求められることを示せば十分.
というわけで手元に
を満たす決定性の敵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)としましょう.
すると,
を満たすDが存在すると考えてもいいわけです.
ここまでが前提です.
次にちょっと横道にそれてフーリエ変換の話を始めます.
F=F2nの離散フーリエ変換
関数fを要素としてもつ環V={f:F→R}を考えます. 和と積は項別に計算することにして演算を入れてあります.
この環に内積をという定義で入れます.
関数のノルムは内積の2乗ということにします.
するとf:F→{-1,+1}はノルムが必ず1になります.
次にフーリエ基底を用意します.
関数族{χx}x∈Fただし, です.
定義より, χxのノルムは1です.
簡単な計算により, 任意のx≠x'で<χx, χx'>=0が言えます.
従って, この関数族はベクトル空間Vの正規直交基底になっています.
内積やノルムを入れた御利益として以下があります.
- g'(x) = <g, χx>と定義します. (gのフーリエ係数.)
- g(r) = Σx g'(x) χx(r)が成立します.
- ||g||2 = Σx g'2(x) = 1です.
合流
さて, 先ほど見たように, 今
を満たすDxが存在すると考えています.
面倒なので, g(r)=Dx(r)と置いて, b'(x,r)=χx(r)に注意すると,
.
書き直すと,
.
従って,
が成立することになります.
以上より, xを求める問題だったのが, g(r)=D(f(x),r)の大きなフーリエ係数を求める問題に変わりました.
ありがたいことに, そのようなフーリエ係数の個数は高々1/ε2個しか無いこともノルムの議論から証明出来ます.
ここから先は頑張ってKushilevitz and Mansourなり, Akavia, Goldwasser, and Safraを読んでください. 以上.