|
|
|
|
|
Hard Core PredicateIn 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 1-1 function has a hard core predicate, then it must be one way. Goldreich and 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 for all . Define - g(x, r) = (f(x), r),
where the length of r is the same as that of x. Let denote the jth bit of x and the jth bit of r. Then -
is a hard core predicate of g. 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 may reveal correlations between certain bits of without revealing anything about individual bits. Hard core predicates give a way to construct a pseudorandom sequence from any one way function. If b is a hard core predicate of a one way function f, and s is a random seed, then -
is a pseudorandom bit sequence. References
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|