We construct a secure protocol for any multi-party functionality that remains secure (under a relaxed definition of security introduced by Prabhakaran and Sahai (STOC ?04)) when executed concurrently with multiple copies of itself and other protocols, without any assumptions on existence of trusted parties, common reference string, honest majority or synchronicity of the network. The relaxation of security is obtained by allowing the ideal-model simulator to run in quai-polynomial (as opposed to polynomial) time. Quasipolynomial simulation suffices to ensure security for most applications of multi-party computation. Furthermore, Lindell (FOCS ?03, TCC? 04) recently showed that such a protocol is impossible to obtain under the more standard defi- nition of polynomial-time simulation by an ideal adversary.

Our construction is the first such protocol under reasonably standard cryptographic assumptions (i.e., existence of a hash function collection that is collision resistent with respect to circuits of subexponential size, and existence of trapdoor permutations which are secure with respect to circuits of quasi-polynomial size).

We introduce a new technique: "protocol condensing". That is, taking a protocol that has strong security properties but requires super-polynomial communication and computation, and then transforming it into a protocol with polynomial communication and computation, that still inherits the strong security properties of the original protocol. Our result is obtained by combining this technique with previous techniques of Canetti, Lindell, Ostrovsky, and Sahai (STOC ?02) and Pass (STOC ?04).