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