ハードコア述語

ハードコア述語とは

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

• 出典: フリー百科事典『ウィキペディア（Wikipedia）』
• [ ハードコア述語の改定履歴 ]