# Sub exponentially hard OWF , PRF and iO

I'm currently reading the work "Obfuscation of probabilistic circuits and Applications' by Canetti Lin Tessaro and Vaikuntanathan 2015. It says sub exponentially hard OWF implies sub exponentially hard PRF ( puncturable PRF) and later again proves that sub exponentially hard PRF ( puncturable PRF) + sub exponentially hard iO $\implies$ pIO(probabilistic circuits).

I'm really confused with what the author means by the term "subexponentially hard" and is it a weather or a stronger assumption when it comes to the OWF or iO.

• What's the difference between this question and this question? – puzzlepalace Apr 7 '17 at 18:31
• Note that there is a mistake in the question: subexp prf does not imply subexp iO. – Geoffroy Couteau Apr 7 '17 at 20:06

An efficiently computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ is said to be $(s,\epsilon)$-one-way if for every adversary $\mathsf{A}$ of size* at most $s=s(|x|)$ the probability $\Pr\left[{\mathsf{A}(f(x))\in f^{-1}(x)}\right]$ is at most $\epsilon=\epsilon(|x|)$, where the probability is over uniform distribution on the domain and the random coins of $\mathsf{A}$.

The standard one-wayness assumption is that $s=poly(|x|)$ and $\epsilon=negl(|x|)$ . A one-way function is subexponentially-hard if for a fixed constant $0<c<1$, it is $(2^{{|x|}^c},2^{-{|x|}^c})$-one-way. Note that the latter implies the former and is, therefore, a stronger assumption.

Similar definitions apply for the other primitives too.

*Here, size refers either to the run-time if $\mathsf{A}$ is a probabilistic Turing machine, or the circuit-size in case $\mathsf{A}$ is a circuit.

• They will become equivalent if ​ $\omega \hspace{.02 in}(1)$ ​ bits of non-uniformly are allowed, but otherwise, $\hspace{.91 in}$ one needs to replace the ​ o(1) s ​ with c and assert the existence of a positive $\hspace{1.38 in}$ constant c before quantifying over the adversaries. ​ ​ ​ ​ – user991 Apr 8 '17 at 3:36
• @DheerajMPai : ​ See my previous comment. ​ ​ ​ ​ – user991 Apr 8 '17 at 3:37
• @RickyDemer: I have made the change you suggested. 1.) Is it correct now? 2.) Could you elaborate your comment (i.e., how non-uniformity leads to equivalence) --- I don't quite grasp the difference. – Occams_Trimmer Apr 8 '17 at 12:50
• "that the" ​ should be replaced with ending the sentence and starting a new sentence. ​ Otherwise, it seems to be correct now. ​ I wrote up a proof here. ​ ​ ​ ​ – user991 Apr 8 '17 at 13:47
• Are $1 \over s$ and $\epsilon$ interchangeable? Essentially this question crypto.stackexchange.com/questions/46545/… . @RickyDemer – user38956 Apr 12 '17 at 13:40