|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 述語 ： [じゅつご] (n) predicate ・ 語 ： [ご] 1. (n,n-suf) language 2. word
暗号理論において、一方向性関数 ''f'' に関するハードコア述語（ハードコアじゅつご、Hard-core predicate）とは、''x'' からは簡単に計算出来るが ''f''(''x'') から計算するのは難しい述語 ''b'' のことである。より正確には、''x'' をランダムに選んだとき ''f''(''x'') から ''b''(''x'') を 1/2 以上の有意な確率で計算できる確率的多項式時間アルゴリズムが存在しないとき、''b'' を ''f'' のハードコア述語と呼ぶ。ハードコア関数も同様にして定義される（ただし弱いものと強いものがある）。 ハードコア述語は、関数 ''f'' を逆算するときに「一番難しいところ」を捉えた概念である。 一方向性関数は逆算するのが難しい。しかし像 ''f''(''x'') から原像 ''x'' の部分的な情報 ''c'' を得ることについては何も言及していない。例えば、RSA関数は一方向性関数だと予想されているが、原像のヤコビ記号は像から簡単に求められる。 == 厳密な定義 == 述語 が以下を満たすとき、関数 ''f'' のハードコア述語であるという: # ''b'' は多項式時間で計算可能。すなわちある多項式時間アルゴリズム ''B'' が存在して, 。 # 任意の多項式サイズ回路族 について, ある無視可能函数 ε が存在し, 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ハードコア述語」の詳細全文を読む スポンサード リンク
|