Hard-core predicate

Incryptography,ahard-core predicateof aone-way functionfis apredicateb(i.e., a function whose output is a single bit) which is easy to compute (as a function ofx) but is hard to compute givenf(x).In formal terms, there is noprobabilistic polynomial-time (PPT) algorithmthat computesb(x)fromf(x)with probabilitysignificantly greaterthan one half over random choice ofx.In other words, ifxis drawn uniformly at random, then givenf(x),any PPT adversary can only distinguish the hard-core bitb(x)and a uniformly random bit with negligibleadvantageover the length ofx.

Ahard-core functioncan be defined similarly. That is, ifxis chosen uniformly at random, then givenf(x),any PPT algorithm can only distinguish the hard-core function valueh(x)and uniformly random bits of length|h(x)|with negligible advantage over the length ofx.

A hard-core predicate captures "in a concentrated sense" the hardness of invertingf.

While a one-way function is hard to invert, there are no guarantees about the feasibility of computing partial information about thepreimagecfrom the imagef(x).For instance, whileRSAis conjectured to be a one-way function, theJacobi symbolof the preimage can be easily computed from that of the image.

It is clear that if aone-to-one functionhas a hard-core predicate, then it must be one way.Oded GoldreichandLeonid 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.Letfbe a one-way function. Defineg(x,r) = (f(x), r)where the length ofris the same as that ofx.Letx_jdenote thej^thbit ofxandr_jthej^thbit ofr.Then

$b(x,r):=\langle x,r\rangle =\bigoplus _{j}x_{j}r_{j}$

is a hard core predicate ofg.Note thatb(x, r)= <x, r> where <·, ·> denotes the standardinner producton thevector space(Z₂)ⁿ.This predicate is hard-core due to computational issues; that is, it is not hard to compute becauseg(x, r)isinformation theoreticallylossy. Rather, if there exists an algorithm that computes this predicate efficiently, then there is another algorithm that can invertfefficiently.

A similar construction yields a hard-core function withO(log |x|)output bits. Supposefis a strong one-way function. Defineg(x, r)=(f(x), r)where |r| = 2|x|. Choose a length functionl(n)=O(log n)s.t.l(n)≤n.Let

$b_{i}(x,r)=\bigoplus _{j}x_{j}r_{i+j}.$

Thenh(x, r):=b₁(x, r) b₂(x, r)... b_l(|x|)(x, r)is a hard-core function with output lengthl(|x|).

It is sometimes the case that an actual bit of the inputxis hard-core. For example, every single bit of inputs to the RSA function is a hard-core predicate of RSA and blocks ofO(log |x|)bits ofxare indistinguishable from random bit strings in polynomial time (under the assumption that the RSA function is hard to invert).

Hard-core predicates give a way to construct apseudorandom generatorfrom anyone-way permutation.Ifbis a hard-core predicate of a one-way permutationf,andsis a random seed, then

$\{b(f^{n}(s))\}_{n}$

is a pseudorandom bit sequence, wherefⁿmeans the n-th iteration of applyingfons,andbis the generated hard-core bit by each roundn.

Hard-core predicates of trapdoor one-way permutations (known astrapdoor predicates) can be used to constructsemantically securepublic-key encryption schemes.

See also

• List-decoding(describes list decoding; the core of the Goldreich-Levin construction of hard-core predicates from one-way functions can be viewed as an algorithm for list-decoding theHadamard code).

References

• Oded Goldreich,Foundations of Cryptography vol 1: Basic Tools,Cambridge University Press, 2001.