Talk:Hard-core predicate

From Wikipedia, the free encyclopedia

You have new messages (last change).

There's a new paper The security of all RSA and discrete log bits whose abstract states that:

  • all bits of RSA and discrete log are hard core
  • every block of log |x| bits is simultaneously hard core

which is very relevant and very exciting; I haven't read the paper yet; the article needs to be updated. Arvindn 07:35, 18 Nov 2004 (UTC)

Yep, this has actually been known for awhile, it's just now appearing in journal form. I can try to take a crack at some point in the near future. --Chris Peikert 20:36, 18 Nov 2004 (UTC)

This question concerns blackbox one-way functions and computable one-way functions. [I use slightly different notation - g is used to indicate the hard-core predicate instead of B]

Let f:\{0,1\}^* \mapsto \{0,1\}^* be a length-preserving one-way function, and

Let g:\{0,1\}^* \mapsto \{0,1\} be the hardcore predicate of f.

Due to the Goldreich-Levin theorem, such a hardcore predicate exists for all length-preserving one-way functions.

We define the probabilities

u = \Pr[ x \leftarrow\{0,1\}^* ; y\leftarrow f(x): A(y, f(.)) \rightarrow g(x)] and v = \Pr[ x \leftarrow\{0,1\}^* ; y\leftarrow f(x): A(y, B(f(.)) \rightarrow g(x)]

Here: f(.) represents the algorithm for computing} f

B(f(.)) represents a blackbox for computing f

x is a finite length string chosen uniformly from {0,1} * , and

A is any PPT algorithm.

The Goldreich-Levin theorem says that if f is one-way, then for all algorithms A, the probability u is negligible function of | x | . Thus, v is also a negligible function of | x | .

However, the Goldreich-Levin theorem does not say anything about the ratio k = v / u.

My question: Is k a negligible function of | x | too? According to my logic, k should be close to 1, and should be independent of x.

Observation: If k = 1 then having access to the algorithm of f does not give any additional advantage over having blackbox access to f (in computing the hard-core predicate)

Retrieved from "http://en.wikipedia.org../../../h/a/r/Talk%7EHard-core_predicate_bd72.html"