Score:2

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

cn flag

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"

Score:4
ng flag

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

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.