I have been reading a paper where they construct probabilistic IO (indistinguishability obfuscation) from sub exponential IO. I want to know if the following two notions of sub-exponential security equivalent?

  1. A scheme is sub-exponentially secure if a PPT adversary doesn't get more than 1/subexp(x) advantage.

  2. A scheme is sub-exponentially secure if an adversary with sub-exponential computational power doesn't get more than negligible(x) advantage.

(x is security parameter)

The paper defines sub exp secure as defined in 1. But I have come across several notions where they define definition 2 for sub-exponential secure scheme.

Please clarify if both are equivalent. If yes please let me know the proof. If not then where does the equivalence fail?

  • $\begingroup$ What is "io"? It'd make your question understandable for those who don't like clicking on links. $\endgroup$
    – kodlu
    Commented Apr 12, 2017 at 22:45
  • 1
    $\begingroup$ IO means indistinguishability Obfuscation. It is the topic on which current Cryptographic research is going on. As it was recent topic there are not much information on web. But I'll soon create a wiki for the same in SE as well as on Wikipedia. I'm really sorry for that.@kodlu $\endgroup$
    – user38956
    Commented Apr 14, 2017 at 5:35
  • 1
    $\begingroup$ Does the paragraph after Def. 2.1 answer your question? $\endgroup$
    – K.G.
    Commented Apr 14, 2017 at 9:54
  • 2
    $\begingroup$ Retry subexponentially many times and get non-negligible success. $\endgroup$
    – LeoDucas
    Commented Apr 15, 2017 at 6:43
  • 1
    $\begingroup$ @DanielApon Just making a claim about super-polynomial time adversaries doesn't make it stronger, does it? You can make a claim like "every exponential-time adversary has advantage 1", which is not very strong. $\endgroup$ Commented Apr 19, 2017 at 6:44

1 Answer 1


Since noone has written down an answer, I'll give it a go.

There are two important parts of your (or of any) security definitions:

  1. An adversary $\mathcal{A}$, with bounded computational power;
  2. A bound ${\tt negl}(x)$ on the advantage of $\mathcal{A}$.

These lead to two important observations:

  1. The more power we give $\mathcal{A}$, the stronger our security notion;
  2. The tighter ${\tt negl}(x)$, the stronger our security notion.

Ideally, you'd give $\mathcal{A}$ unlimited power, and show that he can achieve 0 advantage.

What does this look like in your definitions? Let's first consider $\mathcal{A}$. In (1), your adversary has polynomial computing power. In (2), your adversary has sub-exponential computational power. From this perspective, (2) makes a weaker assumption on the adversary, and thus would provide a stronger security guarantee than (1).

But as mentioned, the security does not only depend on the adversary. In (1), the function ${\tt negl}_1(x)=1/{\tt subexp}(x)$. In (2), there is no definition of ${\tt negl}_2$. I'd say there are two options:

  1. ${\tt negl}_2(x)\leq{\tt negl}_1(x)$. Then (2) makes a weaker assumption on the adversary and has a tighter bound on the advantage. Thus (2) gives a stronger security guarantee.
  2. ${\tt negl}_2(x)\gt{\tt negl}_1(x)$. Now (2) makes a weaker assumption on the adversary, but (1) has a tighter bound on the advantage. In this case I'd say neither is better. It's basically saying "if we give the adversary more power, he can get more advantage". It would probably depend on context which of the two is applicable.

Edit: I may have misunderstood your question, if you mean (2) to have negligible advantage according to the usual definition. In that case the above is probably obvious to you, and does not help at all towards your question. I guess I'll just leave it in case it helps someone else..

  • $\begingroup$ In (2) negligible is probably taken to be the usual definition of a negligible function, i.e. $< \frac{1}{\mathrm{poly}(x)}$ for all polynomials. $\endgroup$
    – Mark
    Commented Apr 15, 2017 at 15:53
  • $\begingroup$ @Mark I guess so, just didn't want to make the assumption. Also, anyone care to elaborate on the downvote? $\endgroup$ Commented Apr 15, 2017 at 16:02
  • $\begingroup$ Considering what Mark mentioned in his comment. Can you say one of the above definition is stronger than the other? @CurveEnthusiast $\endgroup$
    – user38956
    Commented Apr 18, 2017 at 18:59
  • $\begingroup$ @DheerajMPai I'm not completely agreeing with Leo's and Anton's comments. But since I don't consider myself an expert here, I'm reluctant to present my version as the right one. At least using the arguments in my answer, you cannot decide which is stronger. $\endgroup$ Commented Apr 19, 2017 at 6:41

Your Answer

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