The notion of sub-exponential security

Question

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?

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