We construct a secure protocol for any multi-party functionality
that remains secure (under a relaxed definition of security) when
executed concurrently with multiple copies of itself and other
protocols. We stress that we do *not* use any assumptions on
existence of trusted parties, common reference string, honest
majority or synchronicity of the network. The relaxation of
security, introduced by Prabhakaran and Sahai (STOC '04), is
obtained by allowing the ideal-model simulator to run in
*quai-polynomial* (as opposed to polynomial) time.
Quasi-polynomial 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 definition of
*polynomial-time* simulation by an ideal adversary.

Our construction is the first such protocol under reasonably
standard cryptographic assumptions. That is, existence of a hash
function collection that is collision resistent with respect to
circuits of subexponential size, and existence of trapdoor
permutations that 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).