Hard-core predicate (original) (raw)
暗号理論において、一方向性関数 f に関するハードコア述語（ハードコアじゅつご、Hard-core predicate）とは、x からは簡単に計算出来るが f(x) から計算するのは難しい述語 b のことである。より正確には、x をランダムに選んだとき f(x) から b(x) を 1/2 以上の有意な確率で計算できる確率的多項式時間アルゴリズムが存在しないとき、b を f のハードコア述語と呼ぶ。ハードコア関数も同様にして定義される（ただし弱いものと強いものがある）。 ハードコア述語は、関数 f を逆算するときに「一番難しいところ」を捉えた概念である。 一方向性関数は逆算するのが難しい。しかし像 f(x) から原像 x の部分的な情報 c を得ることについては何も言及していない。例えば、は一方向性関数だと予想されているが、原像のヤコビ記号は像から簡単に求められる。
| Property | Value | |||
|---|---|---|---|---|
| dbo:abstract | In cryptography, a hard-core predicate of a one-way function f is a predicate b (i.e., a function whose output is a single bit) which is easy to compute (as a function of x) but is hard to compute given f(x). In formal terms, there is no probabilistic polynomial-time (PPT) algorithm that computes b(x) from f(x) with probability significantly greater than one half over random choice of x. In other words, if x is drawn uniformly at random, then given f(x), any PPT adversary can only distinguish the hard-core bit b(x) and a uniformly random bit with negligible advantage over the length of x. A hard-core function can be defined similarly. That is, if x is chosen uniformly at random, then given f(x), any PPT algorithm can only distinguish the hard-core function value h(x) and uniformly random bits of length |h(x) | with negligible advantage over the length of x. A hard-core predicate captures "in a concentrated sense" the hardness of inverting f. While a one-way function is hard to invert, there are no guarantees about the feasibility of computing partial information about the preimage c from the image f(x). For instance, while RSA is conjectured to be a one-way function, the Jacobi symbol of the preimage can be easily computed from that of the image. It is clear that if a one-to-one function has a hard-core predicate, then it must be one way. Oded Goldreich and Leonid Levin (1989) showed how every one-way function can be trivially modified to obtain a one-way function that has a specific hard-core predicate. Let f be a one-way function. Define g(x,r) = (f(x), r) where the length of r is the same as that of x. Let xj denote the jth bit of x and rj the jth bit of r. Then is a hard core predicate of g. Note that b(x, r) = <x, r> where <·, ·> denotes the standard inner product on the vector space (Z2)n. This predicate is hard-core due to computational issues; that is, it is not hard to compute because g(x, r) is information theoretically lossy. Rather, if there exists an algorithm that computes this predicate efficiently, then there is another algorithm that can invert f efficiently. A similar construction yields a hard-core function with O(log | x | ) output bits. Suppose f is a strong one-way function. Define g(x, r) = (f(x), r) where |
| dbo:wikiPageID | 1182871 (xsd:integer) | |||
| dbo:wikiPageLength | 6095 (xsd:nonNegativeInteger) | |||
| dbo:wikiPageRevisionID | 1092416759 (xsd:integer) | |||
| dbo:wikiPageWikiLink | dbr:Bounded-error_probabilistic_polynomial dbr:Vector_space dbr:Jacobi_symbol dbr:Cryptography dbr:One-way_function dbr:Leonid_Levin dbr:CSPRNG dbr:Hadamard_code dbr:Semantic_security dbr:Advantage_(cryptography) dbc:Theory_of_cryptography dbc:Pseudorandomness dbr:Information_theory dbr:Injective_function dbr:Inner_product_space dbr:Oded_Goldreich dbr:RSA_(algorithm) dbr:Predicate_(mathematics) dbr:Preimage dbr:List-decoding dbr:One-way_permutation dbr:Negligible_function_(cryptography) | |||
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Rp | |||
| dct:subject | dbc:Theory_of_cryptography dbc:Pseudorandomness | |||
| gold:hypernym | dbr:Predicate | |||
| rdfs:comment | 暗号理論において、一方向性関数 f に関するハードコア述語（ハードコアじゅつご、Hard-core predicate）とは、x からは簡単に計算出来るが f(x) から計算するのは難しい述語 b のことである。より正確には、x をランダムに選んだとき f(x) から b(x) を 1/2 以上の有意な確率で計算できる確率的多項式時間アルゴリズムが存在しないとき、b を f のハードコア述語と呼ぶ。ハードコア関数も同様にして定義される（ただし弱いものと強いものがある）。 ハードコア述語は、関数 f を逆算するときに「一番難しいところ」を捉えた概念である。 一方向性関数は逆算するのが難しい。しかし像 f(x) から原像 x の部分的な情報 c を得ることについては何も言及していない。例えば、は一方向性関数だと予想されているが、原像のヤコビ記号は像から簡単に求められる。 (ja) В криптографии, трудным предикатом для односторонней функции называется функция , принимающая значение 0 или 1, при этом её значение легко вычислить зная , и трудно вычислить зная лишь . Формально, полиномиально вычислимая функция является трудным предикатом для функции , если случайная величина трудно вычислима по случайной величине , где — случайная величина, равномерно распределённая на . (ru) In cryptography, a hard-core predicate of a one-way function f is a predicate b (i.e., a function whose output is a single bit) which is easy to compute (as a function of x) but is hard to compute given f(x). In formal terms, there is no probabilistic polynomial-time (PPT) algorithm that computes b(x) from f(x) with probability significantly greater than one half over random choice of x. In other words, if x is drawn uniformly at random, then given f(x), any PPT adversary can only distinguish the hard-core bit b(x) and a uniformly random bit with negligible advantage over the length of x. (en) | |||
| rdfs:label | Hard-core predicate (en) ハードコア述語 (ja) Трудный бит (ru) | |||
| owl:sameAs | freebase:Hard-core predicate wikidata:Hard-core predicate dbpedia-he:Hard-core predicate dbpedia-ja:Hard-core predicate dbpedia-ru:Hard-core predicate https://global.dbpedia.org/id/2EFVU | |||
| prov:wasDerivedFrom | wikipedia-en:Hard-core_predicate?oldid=1092416759&ns=0 | |||
| foaf:isPrimaryTopicOf | wikipedia-en:Hard-core_predicate | |||
| is dbo:wikiPageRedirects of | dbr:Trapdoor_predicate dbr:Hard-core_bit dbr:Hard_core_bit dbr:Hard_core_predicate dbr:Goldreich-Levin_Construction dbr:Goldreich-Levin_bit dbr:Goldreich-Levin_construction dbr:Goldreich-Levin_theorem | |||
| is dbo:wikiPageWikiLink of | dbr:Index_of_cryptography_articles dbr:Commitment_scheme dbr:Julia_Wolf dbr:List_decoding dbr:Randomness_extractor dbr:Hardcore dbr:Pseudorandom_generator_theorem dbr:Trapdoor_predicate dbr:Hard-core_bit dbr:Hard_core_bit dbr:Hard_core_predicate dbr:Goldreich-Levin_Construction dbr:Goldreich-Levin_bit dbr:Goldreich-Levin_construction dbr:Goldreich-Levin_theorem | |||
| is foaf:primaryTopic of | wikipedia-en:Hard-core_predicate |