# Prove: If there exist strong OWFs then there exist weak OWFs that aren't strong

Assume there exist strong OWFs, then there exist functions that are weak $$\frac{2}{3}$$-one-way functions, but not strong one-way ones

Proof

Let $$f$$ be a strong OWF. Define $$g(x) = \begin{cases} (1, f(x)) & x_1 = 1 \\ 0 & else \end{cases}$$

I just don't understand if $$x_1$$ is the first bit in x here? And if so, where is the possibility $$\leq \frac{2}{3}$$ gotten from?

Two things:

1. Yes, $$x_1$$ is the first bit. The idea is that if $$x_1 = 0$$ (which occurs with probability 1/2), it is simple to find a preimage of $$g(x) = 0$$ --- any string $$x'$$ with $$x'_1 = 0$$ will suffice. This shows that $$g$$ cannot be an $$\alpha$$-OWF for any $$\alpha <1/2$$. To show that it is an $$\alpha$$-OWF for $$\alpha \leq 2/3$$, you would need to reduce to the strong OWF security of $$f$$, which I will leave for you to do.

2. The choice of $$2/3$$ is simply a social convention for a "suitable constant". There are many complexity classes $$\mathcal{C}$$ that depend on some parameter $$\alpha$$ (which I will denote $$\mathcal{C}(\alpha)$$) where you can show some result of the form

For any $$\alpha$$ bounded away* from $$1/2$$ and $$1$$, the complexity classes $$\mathcal{C}(\alpha)$$ are equivalent.

Here, "bounded away" means that $$\frac{1}{2}+\frac{1}{n^c} \leq \alpha \leq 1 - \frac{1}{n^d}$$ for constants $$c, d$$ --- in particular, $$\alpha$$ cannot be negligibly close (as a function of the size of the input) to either 1/2 or 1. For such classes, the social convention to choose $$\mathcal{C}(2/3)$$ as the "standard" example to relate things to is common.

There are many examples of the above phenonoma, for example most randomized complexity classes, but perhaps $$BPP$$ in particular is the best-known example. The importance of $$\alpha$$ being bounded away from 1/2 and 1 can be seen via the difference between the classes $$BPP$$ (which has this restriction), and the class $$PP$$ (which doesn't, and is much more powerful).

Anyway, this section of the linked notes are essentially showing that one-way functions are a similar class to things like $$BPP$$ (in terms of their dependence on a parameter $$\alpha$$).