Hard-core predicate

From Wikipedia, the free encyclopedia

In cryptography, a hard-core predicate of a one-way function f(x) is a predicate b(x) which is easy to compute given x but is hard to compute given f(x). In formal terms, there is no probabilistic polynomial time algorithm that computes b(x) from f(x) with probability significantly greater than one half.

A hard-core predicate captures "in a concentrated sense" the hardness of inverting f. More generally, a hard-core function is a function that has the same property.

While a one-way function is hard to invert, it makes no guarantees about the feasibility of computing partial information about the preimage. 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.

Therefore a one-way function alone is not sufficient for encryption. This notion is called semantic security. Hard-core predicates are used to get around this problem; for instance see probabilistic encryption.

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 length-preserving one-way function can be trivially modified so that it has a specific hard-core predicate. Let f be a length-preserving one-way function, that is, one for which $| f (x) | = | x |$ for all $x$ . Define

g(x, r) = (f(x), r),

where the length of r is the same as that of x. Let $x j$ denote the j^th bit of x and $r j$ the j^th bit of r. Then

$b(x, r) = \bigoplus_j x_j r_j$

is a hard core predicate of g. Note that $b(x,r) = \langle x, r\rangle$ where $\langle \cdot, \cdot \rangle$ denotes the standard inner product on the vector space $(\Z/2\Z)^n$ . A similar construction yields a hard-core function with log (|x|) output bits.

It is often the case that an actual bit of x is hard-core, such as last bit of RSA is hard-core. It is in fact conjectured that the latter half of the bits are all hard-core for RSA; in other words, the latter-half bits constitute a hard-core function. Note that this is stronger than each of the latter bits being hard-core predicates individually, because $f (x)$ may reveal correlations between certain bits of $x$ without revealing anything about individual bits.

Hard-core predicates give a way to construct a pseudorandom sequence from any one-way permutation. If b is a hard-core predicate of a one way function f, and s is a random seed, then

$\left \{ b ( f^n ( s ) ) \right \}_n$

is a pseudorandom bit sequence.

[edit] References

Oded Goldreich and Leonid A. Levin, A Hard-Core Predicate for all One-Way Functions, STOC 1989, pp25–32.

Retrieved from "http://en.wikipedia.org../../../h/a/r/Hard-core_predicate.html"

Category: Theory of cryptography

Hard-core predicate

From Wikipedia, the free encyclopedia

[edit] References

Views

Navigation

Search