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 - 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
Here: represents the algorithm for computing}
represents a blackbox for computing
is a finite length string chosen uniformly from , and
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)