I try to get the intuition behind the notion of strong one way function and weak one way function by reading the scribe One-Way Functions. Particularly, I am interested in examples and definitions of the weak and strong one way function. I known it's very broad notion, therefore I will be as specific as possible in my questions.

Strong one way function. $\forall$ nonuniform PPT $A$, $\exists \epsilon s.t. \forall n \in N, Pr_{x\in\{0,1\}^n}[A(1^n, f(x)) \in f^{-1}(f(x))] \leq \epsilon(n)$

Q:$1^n$ as the first parameter of the PPT $A$ represent the length of the initial input, the usage of it is justified as "this ensures that the output of A doesn't shrink the size if its too must as in the f(x)=|x| example". Unfortunately I didn't get the previous explanation (may be because the lost the sign, which takes an additional bit). In my opinion putting in A the size of $x$ might help $A$ get the right output $x$.

Q: in the lecture it mentioned that $f(x)=|x|$ is hard, "because it will take $2^c$ time to write a valid inverse of something such that $f(x)=c$". It happens because we cannot find $x$ with probability with negligible more than 0.5, but it's due to another problem not a computational but rather information theory problem, by running the function we lost the information about the sign of the input $x$, if it's a correct reasoning, why actually it would take $2^c$ time? In addition for me it looks like the great discover to find the strong one way function, however do have more assumption of hard function like $f(x)=|x|$?

Definition of weak one way function.$\exists$ $q(x)$, $\forall$ nonunoform PPT A, $\forall$ n $\in$ N, $Pr_{x \in \{0,1\}^n}[A(1^n,f(x)) \in f^{-1}(f(x))] \leq 1-\frac{1}{q(n)}$

Q: in the lecture there was an assumption that the multiplication is weak one function, how we can actually show that the multiplication is weak one way function, and do we have more assumptions of examples of weak one way functions?

I am very sorry for being naive, even though I will appreciate any help.


As for your first question, the reason behind adding $1^n$ as an input to $A$ is to allow it a running time of (at least) a polynomial in $n$. In most applications of one-way functions, $n$ is not a secret, so there is no reason to hide it; in fact, for most functions you can determine $n$ from the output size.

To see what fails if we leave $1^n$ out, consider the situation in the second question. You're misreading the notation - $|x|$ is the length of the string $x$. If $x$ is $n$ bits long then $|x|$ is $O(\log n)$ bits long, and so no machine can find a preimage in time polynomial in $|x|$. However, it is easy to find a preimage in time polynomial in $n$. Add ing$1^n$ as a parameter to the adversary $A$ ensures that $|x|$ is not considered a hard function.

Finally, one-way functions, weak or strong, are not known to exist, even assuming P$\neq$NP. This is similar to the situation in computational complexity, where no worst-case hard functions are known. However, some functions are conjectured to be one-way - ask your professor for their favorite ones.


The reason for the $1^n$ is explained here: Why does key generation take an input 1k, and how do I represent it in practice?. Please read that answer for further explanation. This is a standard trick in complexity-theoretic cryptography, and on first reading you can ignore it and focus on the conceptual aspects of the definition.


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.