3
$\begingroup$

I'm considering the following definition of one-way functions:

Let $f : \{0,1\}^k \rightarrow \{0,1\}^k$ and $b : \{0,1\}^k \rightarrow \{0,1\}$ be computable in poly($k$) time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all polynomial-time randomized algorithms $A$ and all constants $c$, $$\underset{x\in\{0,1\}^k}{\mathbb{E}}\Big[\mathbb{P}[A(f(x))=b(x)]\Big]=\frac{1}{2}+o(k^{-c})$$

Note that $A(f(x))=b(x)$ is an event, not because $x$ is random but because $A$ is a randomized algorithm.
Now suppose $f$ isn't a one-way function, then this expectation will be noticeably different from $1/2$. But for any particular $x$ the probability might still be close to $1/2$. Indeed the probability could be exactly $1/2$ (or even 0) for a large fraction of the $x$, provided for the remaining $x$ $f(x)$ can be inverted with sufficient accuracy to make the expectation noticeably different from $1/2$ again.
So what do I do if I'm presented with such an $f(x)$? The fact that many other $f(x)$ can easily be inverted seems of little consolation then. I don't see any way to invert $f$ then. In particular in connection with pseudorandom number generators I'm reading statements like

We will show that if any tester $A$ can tell the difference between $g(x) = (f(x),\,b(x))$ and a random string, then we can use $A$ to "break" our one-way function, and calculate $b(x)$ from $f(x)$ with $1/\text{poly}(k)$ probability.

I can read this in two different ways.

  1. $x$ is random and there's a $1/\text{poly}(k)$ chance of getting an $x$ for which $b(x)$ can be computed from $f(x)$ exactly.
  2. For every $x$ $b(x)$ can be computed from $f(x)$ with a $1/\text{poly}(k)$ chance of success.

(1) has the problem that the text presents a randomized algorithm to compute $b(x)$ from $f(x).$ It isn't exact.
(2) is false based on the preceding discussion.

$\endgroup$
  • $\begingroup$ What's the problem if the algorithm isn't exact? $\endgroup$ – xskxzr Mar 15 '18 at 3:16
  • $\begingroup$ @xskxzr The quoted segment makes a probabilistic statement about either the runtime behaviour of some inversion procedure $B$ or the $x$ that's being considered. If you assume that it's the $x$ that's random then $B$ just computes $b(x)$ from $f(x)$. But that sounds like you're saying that $B$ is deterministic when it isn't. $\endgroup$ – Sebastian Oberhoff Mar 15 '18 at 3:29
  • $\begingroup$ The first interpretation also doesn't make sense for the second reason that the text only establishes a claim about the expectation when $x$ is considered random. You can't draw a statement about probabilities from that. (Unless you use something like Markov's inequality. But that is never even hinted.) $\endgroup$ – Sebastian Oberhoff Mar 15 '18 at 3:34
1
$\begingroup$

Both (1) and (2) are possible. (It's also possible to have a combination of them.) It doesn't really matter which holds; either way, that means that $f$ is not one-way.

You say (2) is false because of the preceding discussion, but I'm not exactly sure why you think it is false. One-wayness is not a property of a specific value of $x$; rather, it is a property of a function $f$. And, just because a function $f$ is not one-way doesn't mean it can be inverted for every possible output. If $f$ can be inverted on a significant fraction of outputs, it is not one-way. If $f$ can be inverted on all outputs, with a significant probability, it is not one-way.

Perhaps the confusion comes from a misunderstanding about what the definition of a one-way function is. The definition you quote at the beginning is not the definition of a one-way function. Rather, it's the definition of a hardcore bit.

The part you quoted appears to claim/imply that it is the definition of a one-way function with hardcore bit (which is not the same as the definition of a one-way function). That claim/implication is not correct. The precise statement is that this is the definition of a function with hardcore bit. This definition implies nothing about onewayness. So why did they call it the definition of a one-way function with hardcore bit? I don't know; you'd have to ask the author. But my guess is that this definition is normally only used with functions you already know to be one-way, so there's an implicit assumption that $f$ is already known to be one-way, and given such an $f$, the definition is describing what it means for $b$ to be hardcore for $f$.

You say "suppose $f$ isn't one-way, then this expectation will be noticeably different from 1/2". That actually doesn't follow. You can have a function $f$ that isn't one-way but does have a hardcore bit. Then the expectation will not be noticeably different from 1/2. E.g., consider the function $f$ given by $f(x)=0$: it's not one-way, but it does have a hardcore bit, and the expectation is exactly 1/2.

It sounds like you want to understand one-wayness. If so, hardcore bits are a distraction. You should be looking for the definition of a one-way function and trying to understand that, not looking at the definition of a hardcore bit.

$\endgroup$
  • $\begingroup$ I never claimed that the expectation depends on $x$. I said the probability depends on $x$. I'm referring here to the $\mathbb{P}$ in the body of the expectation. Also I wasn't aware that there was a separate definition for one-way functions. So perhaps I should've written "suppose $b$ isn't a hard-core bit for $f$" instead. Nonetheless, I'm currently in the context of using one-way functions (and hard-core bits) to construct pseudorandom generators. So I think I should stick to this definition. $\endgroup$ – Sebastian Oberhoff Mar 15 '18 at 13:01
  • $\begingroup$ Also when I say "Note that $A(f(x)) = b(x)$ is an event, not because $x$ is random, but because $A$ is a randomized algorithm" I'm trying to prevent people from having the same confusion as me here: math.stackexchange.com/questions/2689662/… $\endgroup$ – Sebastian Oberhoff Mar 15 '18 at 13:12
  • $\begingroup$ @SebastianOberhoff, you're right. My fault. I read too quickly. I've done a major edit to my answer to remove all those incorrect parts. Can you take another read through my answer? Now hopefully it more directly addresses your confusion. $\endgroup$ – D.W. Mar 15 '18 at 16:37
  • $\begingroup$ The proof that is introduced by the quoted segment later arrives at a contradiction by constructing a procedure $B$ for which $\mathbb{E}[\mathbb{P}(B(f(x))=b(x))] = 1/2 + \overline{o(k^{-c})}$ holds. (The left hand side is 1/2 plus something outside $o(k^{-c})$). So in expectation we can do a good job, whereas (2) claims we can always do a good job. $\endgroup$ – Sebastian Oberhoff Mar 16 '18 at 7:02
  • $\begingroup$ Besides I'm not even sure how having a $1/\text{poly}(k)$ chance of success even qualifies as doing a good job. There are no obvious means of checking that you got the right answer for $b(x)$, so producing the right answer with such a probability seems useless. $\endgroup$ – Sebastian Oberhoff Mar 16 '18 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.