2
$\begingroup$

Please help me to understand the proof of the following claim:

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?

Source: "Foundation of Cryptography (0368-4162-01), Lecture 1: One Way Functions, Iftach Haitner, Tel Aviv University, November 1-8, 2011"

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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