ハードコア述語

暗号理論において、一方向性関数 f に関するハードコア述語（ハードコアじゅつご、Hard-core predicate）とは、x からは簡単に計算出来るが f(x) から計算するのは難しい述語 b のことである。より正確には、x をランダムに選んだとき f(x) から b(x) を 1/2 以上の有意な確率で計算できる確率的多項式時間アルゴリズムが存在しないとき、b を f のハードコア述語と呼ぶ。ハードコア関数も同様にして定義される（ただし弱いものと強いものがある）。

ハードコア述語は、関数 f を逆算するときに「一番難しいところ」を捉えた概念である。

一方向性関数は逆算するのが難しい。しかし像 f(x) から原像 x の部分的な情報 c を得ることについては何も言及していない。例えば、RSA関数は一方向性関数だと予想されているが、原像のヤコビ記号は像から簡単に求められる。

述語 $b:\{0,1\}^{*}\to \{0,1\}$ が以下を満たすとき、関数 f のハードコア述語であるという:

b は多項式時間で計算可能。すなわちある多項式時間アルゴリズム B が存在して, $B(x)=b(x)$ 。
任意の多項式サイズ回路族 $\{C_{n}\}$ について, ある無視可能函数 ε が存在し,

$Pr[x\gets _{R}\{0,1\}^{n}:C_{n}(f(x))=b(x)]<{\frac {1}{2}}+\epsilon (n)$

一般的なハードコア述語

一対一関数がハードコア述語を持つならば、一方向性関数であることは自明である。ゴールドライヒ (en:Oded Goldreich) とレビン (Levin) は1989年に任意の一方向性関数を変形した一方向性関数が、ハードコア関数を持つことを示した。今、f を一方向性関数だとする。関数 g を

$g(x,r):=f(x)\circ r$

と定義する（ $\circ$ は連結を表す）。ただし、r の長さは x の長さと同じであるとする。x_j を x の j ビットとし、r_j を r の j ビットとする。このとき、

$b(x,r)=\bigoplus _{j}x_{j}r_{j}$

は g のハードコア述語である。ここで、 $\langle \cdot ,\cdot \rangle$ をベクトル空間 $(\mathbb {Z} /2\mathbb {Z} )^{n}$ 上の標準的な内積とすると、 $b(x,r)=\langle x,r\rangle$ である。f(x) から g(x, r) を 1/2 以上に無視できない確率で計算できるアルゴリズムが存在するならば、x そのものを効率よく求めることができる。同様の構成により、 $\log(|x|)$ ビットの出力を持つハードコア関数を構成することができる。

特定の関数に対するハードコア述語

入力 x の特定のビットがハードコア述語になる場合もある。たとえば、最下位ビットはRSA関数についてハードコアである。NaslundとHastadとは下位のビットがRSA関数についてのハードコア述語になることを示している（上位のビットについても拡張されたハードコア述語になる）。より強い主張として、入力の下半分を返す関数はRSA関数についてのハードコア関数だと予想されている^[1]。これは下半分の各ビットがハードコア述語であるということよりは強い。なぜならば f(x) は x の各々のビットについての情報を漏らすことなく、特定のビット間の相関については情報を漏らしうるからである。