3
$\begingroup$

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.

Thanks in advance

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What's the difference between this question and this question? $\endgroup$
    – puzzlepalace
    Commented Apr 7, 2017 at 18:31
  • $\begingroup$ Note that there is a mistake in the question: subexp prf does not imply subexp iO. $\endgroup$
    – Geoffroy Couteau
    Commented Apr 7, 2017 at 20:06

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 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. ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Apr 8, 2017 at 3:36
  • 1
    $\begingroup$ @DheerajMPai : ​ See my previous comment. ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Apr 8, 2017 at 3:37
  • 1
    $\begingroup$ @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. $\endgroup$
    – ckamath
    Commented Apr 8, 2017 at 12:50
  • $\begingroup$ "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. ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Apr 8, 2017 at 13:47
  • $\begingroup$ Are $1 \over s$ and $\epsilon$ interchangeable? Essentially this question crypto.stackexchange.com/questions/46545/… . @RickyDemer $\endgroup$
    – user38956
    Commented Apr 12, 2017 at 13:40

Your Answer

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