ハードコア関数の誤解(その一)

ハードコア関数について今まで思い違いをしていた点があったので,備忘録として書いておこうと思います.前提から書き始めると長くなってしまったので何回かに分けてポストします.

ハードコア関数というのは暗号理論や計算量理論でしばしば現れる基本的な概念なのですが,基本的には一方向性関数などの持つ計算複雑さを擬似乱数に変換するための道具として用いられます.

簡単に説明すると,ハードコア関数の出力と一方向性関数の出力を対にして出したときに,それが一様乱数と一方向性関数の出力の対と識別できないというものです.この性質から擬似乱数生成器の構成などに利用されます.

もう少し形式的に言うと,ある多項式時間計算可能な関数 h:\{0,1\}^*\rightarrow\{0,1\}^*一方向性関数 f:\{0,1\}^*\rightarrow\{0,1\}^*に対するハードコア関数であるとは入力 x nビット長から一様ランダムに取ったとき, (f(x),h(x)) (f(x),u) u h(x)と同じ長さ上の一様乱数)が計算量理論的識別不可能である,つまり効率の良いアルゴリズムでは区別できない,ことを言います.

任意の一方向性関数に対するハードコア関数の構成方法として Goldreich-Levin の結果が有名です.

  • O. Goldreich and L. Levin,
    • "A Hardcore Predicate for All One-Way Functions," STOC '89.

所謂Goldreich-Levinの定理では,任意の一方向性関数 fに対して新たに f'という関数を f'(x,r)=(f(x),r) x,rは同じ長さ)と定義します.この関数も容易に一方向性関数であることが示せます.Goldreich-Levinの定理は任意の一方向性関数 fから定義された新たな一方向性関数 f'に対して,関数 h(x,r) = \langle x,r\rangleがハードコア述語(出力長が1ビットのハードコア関数)であることを主張しています.ここで, \langle x,r\rangle = \sum_i x_i\cdot r_i x,rを0,1のベクトルとして見たときの内積です.

Goldreich-Levinの定理ではf'のような関数を経由するハードコア述語の一般的構成方法が与えられているわけですが,任意の一方向性関数 fに対するハードコア述語が構成できないのか?と疑問が出てくるかと思いますが,実は付加的な入力rが必要であることは実は証明できてしまうため,任意の一方向性関数 fに対するハードコア述語の直接的構成は存在しません.

次回に続きます.