6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is "io"? It'd make your question understandable for those who don't like clicking on links. $\endgroup$ – kodlu Apr 12 '17 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 Apr 14 '17 at 5:35
  • 1
    $\begingroup$ Does the paragraph after Def. 2.1 answer your question? $\endgroup$ – K.G. Apr 14 '17 at 9:54
  • 1
    $\begingroup$ Retry subexponentially many times and get non-negligible success. $\endgroup$ – LeoDucas Apr 15 '17 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$ – CurveEnthusiast Apr 19 '17 at 6:44
2
+50
$\begingroup$

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

$\endgroup$
  • $\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 Apr 15 '17 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$ – CurveEnthusiast Apr 15 '17 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 Apr 18 '17 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$ – CurveEnthusiast Apr 19 '17 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy