暗号理論において、一方向性関数 "f" に関するハードコア述語（ハードコアじゅつご、Hard-core predicate）とは、"x" からは簡単に計算出来るが "f"("x") から計算するのは難しい述語 "b" のことである。より正確には、"x" をランダムに選んだとき "f"("x") から "b"("x") を 1/2 以上の有意な確率で計算できる確率的多項式時間アルゴリズムが存在しないとき、"b" を "f" のハードコア述語と呼ぶ。ハードコア関数も同様にして定義される（ただし弱いものと強いものがある）。ハードコア述語は、関数 "f" を逆算するときに「一番難しいところ」を捉えた概念である。一方向性関数は逆算するのが難しい。しかし像 "f"("x") から原像 "x" の部分的な情報 "c" を得ることについては何も言及していない。例えば、RSA関数は一方向性関数だと予想されているが、原像のヤコビ記号は像から簡単に求められる。述語 formula_1 が以下を満たすとき、関数 "f" のハードコア述語であるという:一対一関数がハードコア述語を持つならば、一方向性関数であることは自明である。ゴールドライヒ () とレビン (Levin) は1989年に任意の一方向性関数を変形した一方向性関数が、ハードコア関数を持つことを示した。今、"f" を一方向性関数だとする。関数 "g" をと定義する（formula_4は連結を表す）。ただし、"r" の長さは "x" の長さと同じであるとする。"x" を "x" の "j" ビットとし、"r" を "r" の "j" ビットとする。このとき、は "g" のハードコア述語である。ここで、formula_5 をベクトル空間 formula_6 上の標準的な内積とすると、formula_7である。"f"("x") から "g"("x

出典:wikipedia