About: ハードコア述語

暗号理論において、一方向性関数 f に関するハードコア述語（ハードコアじゅつご、Hard-core predicate）とは、x からは簡単に計算出来るが f(x) から計算するのは難しい述語 b のことである。より正確には、x をランダムに選んだとき f(x) から b(x) を 1/2 以上の有意な確率で計算できる確率的多項式時間アルゴリズムが存在しないとき、b を f のハードコア述語と呼ぶ。ハードコア関数も同様にして定義される（ただし弱いものと強いものがある）。 ハードコア述語は、関数 f を逆算するときに「一番難しいところ」を捉えた概念である。 一方向性関数は逆算するのが難しい。しかし像 f(x) から原像 x の部分的な情報 c を得ることについては何も言及していない。例えば、は一方向性関数だと予想されているが、原像のヤコビ記号は像から簡単に求められる。