<p>Well, your edited version of the question revealed a reference to the following paper:</p>
<p>Rafael Pass. 2003. <a href="https://doi.org/10.1007/3-540-39200-9_10" rel="nofollow noreferrer">Simulation in quasi-polynomial time, and its application to protocol composition</a>. In <em>Proceedings of the 22nd international conference on Theory and applications of cryptographic techniques</em> (EUROCRYPT'03), Eli Biham (Ed.). Springer-Verlag, Berlin, Heidelberg, 160-176. (See also <a href="https://web.archive.org/web/20050425014631/http://www.nada.kth.se/%7Erafael/papers/qpolsim.pdf" rel="nofollow noreferrer">this version</a>.)</p>
<p>The paper discusses and justifies the need for such simulators.
The abstract reads:</p>
<blockquote>
<p>We propose a <strong>relaxation</strong> of zero-knowledge, by allowing the
simulator to run in <strong>quasi-polynomial</strong> time. We show that protocols satisfying this notion can be constructed in settings where the standard definition is too restrictive. Specifically, we construct constant-round straight-line concurrent quasi-polynomial time simulatable arguments and show
that such arguments can be used in <strong>advanced composition operations</strong> without any set-up assumptions. Our protocols rely on slightly strong,
but standard type assumptions (namely the existence of one-to-one one-way functions secure against subexponential circuits).</p>
</blockquote>
<p>For a more thorough discussion, I suggest taking a look at Rafael Pass's <a href="http://www.cs.cornell.edu/%7Erafael/papers/raf-lic.pdf" rel="nofollow noreferrer">M.Sc. thesis</a>.</p>

CC BY-SA 2.5
2010-11-20T18:49:47.250Z
I just quote some text from the referenced article   "Security with super-polynomial simulators [SPS](http://portal.acm.org/citation.cfm?id=1766185) is a relaxation of UC security that allows the adversary in the ideal execution to run in super-polynomial time. Informally, this corresponds to guaranteeing that “any poly- time attack that can be mounted against the protocol can also be mounted in the ideal execution—albeit with super- polynomial resources.”
Yasser Sobhdel
CC BY-SA 2.5
2010-11-20T18:50:58.137Z
"Protocols that realize practically any functionality with SPS security in the plain model were shown based on sub-exponential hardness assumptions."  
I think this is more to the point that issues discussed in the Thesis of Pass, but still does not suffice.
Yasser Sobhdel
CC BY-SA 4.0
2010-11-20T16:03:59.107Z
2022-11-24T15:59:32.293Z
2022-11-24T15:59:32.293Z
Sadeq Dousti
<p>One method for proving a protocol secure is through simulation-based models. This simulator uses ideal/real paradigm in which a protocol is secure in the real model if it is proven secure in an ideal model using a trusted third party (you can refer to the Canetti's <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=959888" rel="nofollow">UC framework</a> to realize what is the power and use of this simulator, although use of this simulator dates back to 80s). This simulator is often given polynomial power to simulate the ideal world and if an external entity (observer) cannot distinguish between a real run and a simulated run with probability at most half plus negligible, we say that the protocol is secure or following UC terminology for realizing a functionality, the protocol securely realizes the functionality. It is good to mention that the simulator is also simulating the attacker, so the power of the simulator is essentially power of the attacker. There is often times that the simulator has superpolynomial power.</p>

<blockquote>
  <p><strong>Question</strong>: Does superpolynomial simulator has any advantage over a polynomial simulator? I need a good article on cons and pros of such a simulator.</p>
</blockquote>

<p>A good article in which the author have used a polynomial simulator is <a href="http://www.cs.cornell.edu/~rafael/papers/ccacommit.pdf" rel="nofollow">Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions</a> of Canetti. </p>

CC BY-SA 2.5
2010-11-20T06:48:52.433Z
While I understood what you meant, please specify the context for your question to be of interest for everyone.
Sadeq Dousti
CC BY-SA 2.5
2010-11-20T07:40:07.693Z
And you can start by explaining what a "simulator" is.
Robin Kothari
CC BY-SA 2.5
2010-11-20T10:24:15.960Z
It is now edited. Please see the extra paragraphs above.
Yasser Sobhdel
<cc.complexity-theory><cr.crypto-security>
Superpolynomial Simulator
Yasser Sobhdel
# Superpolynomial Simulator

(Asked by: username_0 on 2010-11-20)

One method for proving a protocol secure is through simulation-based models. This simulator uses ideal/real paradigm in which a protocol is secure in the real model if it is proven secure in an ideal model using a trusted third party (you can refer to the Canetti's [UC framework](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=959888) to realize what is the power and use of this simulator, although use of this simulator dates back to 80s). This simulator is often given polynomial power to simulate the ideal world and if an external entity (observer) cannot distinguish between a real run and a simulated run with probability at most half plus negligible, we say that the protocol is secure or following UC terminology for realizing a functionality, the protocol securely realizes the functionality. It is good to mention that the simulator is also simulating the attacker, so the power of the simulator is essentially power of the attacker. There is often times that the simulator has superpolynomial power.

> **Question**: Does superpolynomial simulator has any advantage over a polynomial simulator? I need a good article on cons and pros of such a simulator.

A good article in which the author have used a polynomial simulator is [Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions](http://www.cs.cornell.edu/~rafael/papers/ccacommit.pdf) of Canetti.

**Tags:** cc.complexity-theory, cr.crypto-security
> **Comments:**
> **username_1**: While I understood what you meant, please specify the context for your question to be of interest for everyone.  
> **username_2**: And you can start by explaining what a "simulator" is.  
> **username_0**: It is now edited. Please see the extra paragraphs above.  

---

## 1 answers

### Answer by username_1 on 2010-11-20. Score: 1 | Accepted answer

Well, your edited version of the question revealed a reference to the following paper:

Rafael Pass. 2003. [Simulation in quasi-polynomial time, and its application to protocol composition](https://doi.org/10.1007/3-540-39200-9_10). In *Proceedings of the 22nd international conference on Theory and applications of cryptographic techniques* (EUROCRYPT'03), Eli Biham (Ed.). Springer-Verlag, Berlin, Heidelberg, 160-176. (See also [this version](https://web.archive.org/web/20050425014631/http://www.nada.kth.se/%7Erafael/papers/qpolsim.pdf).)

The paper discusses and justifies the need for such simulators.
The abstract reads:

> We propose a **relaxation** of zero-knowledge, by allowing the
> simulator to run in **quasi-polynomial** time. We show that protocols satisfying this notion can be constructed in settings where the standard definition is too restrictive. Specifically, we construct constant-round straight-line concurrent quasi-polynomial time simulatable arguments and show
> that such arguments can be used in **advanced composition operations** without any set-up assumptions. Our protocols rely on slightly strong,
> but standard type assumptions (namely the existence of one-to-one one-way functions secure against subexponential circuits).

For a more thorough discussion, I suggest taking a look at Rafael Pass's [M.Sc. thesis](http://www.cs.cornell.edu/%7Erafael/papers/raf-lic.pdf).

> **Comments:**
> **username_0**: I just quote some text from the referenced article   "Security with super-polynomial simulators [SPS](http://portal.acm.org/citation.cfm?id=1766185) is a relaxation of UC security that allows the adversary in the ideal execution to run in super-polynomial time. Informally, this corresponds to guaranteeing that “any poly- time attack that can be mounted against the protocol can also be mounted in the ideal execution—albeit with super- polynomial resources.”  
> **username_0**: "Protocols that realize practically any functionality with SPS security in the plain model were shown based on sub-exponential hardness assumptions."   I think this is more to the point that issues discussed in the Thesis of Pass, but still does not suffice.  

---

