Talk:Hard-core predicate

Latest comment: 13 years ago by RobertHannah89 in topic Recent Discoveries

Recent Discoveries

edit

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 -   is used to indicate the hard-core predicate instead of  ]

Let   be a length-preserving one-way function, and

Let   be the hardcore predicate of  .

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

We define the probabilities

  and  

Here:   represents the algorithm for computing}  

  represents a blackbox for computing  

  is a finite length string chosen uniformly from  , and

  is any PPT algorithm.

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

However, the Goldreich-Levin theorem does not say anything about the ratio  .

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

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