Hardcore predicate
A polynomial-time computable predicate is hardcore for a function if for all efficient ,
is negligible, the probability taken over and the coins of — BM84, Gol01.
An inverter for an injective with success probability predicts with advantage , by outputting when it returns with and a uniform bit otherwise; an efficiently computable injective function with a hardcore predicate is therefore one-way — standard. A non-injective function can have a hardcore predicate for information-theoretic reasons: is hardcore for , which is not one-way — standard.
Goldreich–Levin theorem
For every one-way function , the inner-product predicate , for , is hardcore for — GL89. Quantitatively, let satisfy
Then an algorithm given , making calls to and to and doing further work, outputs a preimage of for with probability — GL89, Gol01.
By averaging over and the coins of , at least an fraction of pairs satisfy . For each such pair, agrees with the Hadamard encoding of on at least a fraction of positions, and the list decoder outputs, with probability at least , a list of candidates containing . Testing each candidate for inverts with probability at least — Gol01.
Simultaneously hardcore bits
Predicates are simultaneously hardcore for if and are computationally indistinguishable, for and uniform on . The Goldreich–Levin theorem extends to simultaneously hardcore inner-product bits, and more generally to a number of bits logarithmic in the security of — GL89. For instance, with independent and , the bits are simultaneously hardcore for : each nonempty XOR is an inner-product bit with a uniform second argument, and the computational XOR lemma of VV84 turns a distinguisher into a predictor for one of these XORs at a loss polynomial in — GL89.
Specific hardcore predicates
- Discrete logarithm. For a prime and a generator of , the half-interval predicate is hardcore for on if DLOG is hard in — BM84. The least significant bit of is not: is even if and only if is a quadratic residue modulo , which Euler’s criterion decides — standard.
- RSA and Rabin. Predicting the least significant bit of from with non-negligible advantage is probabilistic polynomial-time equivalent to inverting RSA, so the least significant bit is hardcore for the RSA function if the RSA assumption holds; the same equivalence holds for the Rabin function on , for a Blum integer , where squaring is a permutation — ACGS88. Inverting the Rabin function is as hard as factoring — Rab79.
Uses
A hardcore predicate of a one-way permutation gives a PRG (OWP ⇒ PRG) — BM84, Yao82a; a hardcore predicate of a trapdoor permutation gives a CPA-secure PKE (TDP ⇒ PKE) — GM84, Yao82a.
Participates in
Used via Hardcore predicate