ハードコア述語
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/29 04:17 UTC 版)
暗号理論において、一方向性関数 f に関するハードコア述語（ハードコアじゅつご、Hard-core predicate）とは、x からは簡単に計算出来るが f(x) から計算するのは難しい述語 b のことである。より正確には、x をランダムに選んだとき f(x) から b(x) を 1/2 以上の有意な確率で計算できる確率的多項式時間アルゴリズムが存在しないとき、b を f のハードコア述語と呼ぶ。ハードコア関数も同様にして定義される（ただし弱いものと強いものがある）。
- ^ Goldreich Ch. 2.7.3 "Foundations of Cryptography vol 1: Basic Tools". J. Haastad, A. Schrift, and A. Shamir. The Discrete Logarithm Modulo a Composite Hides O(n) Bits. Journal of Computer and System Science, Vol. 47, pages 376-404, 1993.
[続きの解説]
「ハードコア述語」の続きの解説一覧
- 1 ハードコア述語とは
- 2 ハードコア述語の概要
- 3 特定の関数に対するハードコア述語
- 4 参考文献
- ハードコア述語のページへのリンク
