一般的なハードコア述語
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/29 04:17 UTC 版)
「ハードコア述語」の記事における「一般的なハードコア述語」の解説
一対一関数がハードコア述語を持つならば、一方向性関数であることは自明である。ゴールドライヒ (en:Oded Goldreich) とレビン (Levin) は1989年に任意の一方向性関数を変形した一方向性関数が、ハードコア関数を持つことを示した。今、f を一方向性関数だとする。関数 g を g ( x , r ) := f ( x ) ∘ r {\displaystyle g(x,r):=f(x)\circ r} と定義する（ ∘ {\displaystyle \circ } は連結を表す）。ただし、r の長さは x の長さと同じであるとする。xj を x の j ビットとし、rj を r の j ビットとする。このとき、 b ( x , r ) = ⨁ j x j r j {\displaystyle b(x,r)=\bigoplus _{j}x_{j}r_{j}} は g のハードコア述語である。ここで、 ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } をベクトル空間 ( Z / 2 Z ) n {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} 上の標準的な内積とすると、 b ( x , r ) = ⟨ x , r ⟩ {\displaystyle b(x,r)=\langle x,r\rangle } である。f(x) から g(x, r) を 1/2 以上に無視できない確率で計算できるアルゴリズムが存在するならば、x そのものを効率よく求めることができる。同様の構成により、 log ( | x | ) {\displaystyle \log(|x|)} ビットの出力を持つハードコア関数を構成することができる。
※この「一般的なハードコア述語」の解説は、「ハードコア述語」の解説の一部です。
「一般的なハードコア述語」を含む「ハードコア述語」の記事については、「ハードコア述語」の概要を参照ください。
- 一般的なハードコア述語のページへのリンク
