Talk:Hard-core predicate

Recent Discoveries

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)

• • Yep. Took a look + added what I understood! RobertHannah89 (talk) 15:07, 27 January 2011 (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)