1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ While I understood what you meant, please specify the context for your question to be of interest for everyone. $\endgroup$ – M.S. Dousti Nov 20 '10 at 6:48
  • 4
    $\begingroup$ And you can start by explaining what a "simulator" is. $\endgroup$ – Robin Kothari Nov 20 '10 at 7:40
  • $\begingroup$ It is now edited. Please see the extra paragraphs above. $\endgroup$ – Yasser Sobhdel Nov 20 '10 at 10:24
1
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ I just quote some text from the referenced article "Security with super-polynomial simulators SPS 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.” $\endgroup$ – Yasser Sobhdel Nov 20 '10 at 18:49
  • $\begingroup$ "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. $\endgroup$ – Yasser Sobhdel Nov 20 '10 at 18:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.