Abstract:

We consider the problem of constructing a secure protocol for
ANY multi-party functionality (for example, electronic auctions,
electronic elections, privacy-preserving data mining). Previous
such constructions either required assuming a third trusted
party or that the protocol is executed in a stand-alone isolated
execution, without more copies of this or other protocols
running in the network.

Under reasonably standard computational assumptions, we
construct a protocol for this problem that is secure (under a
relaxed definition of security) even when executed concurrently
with many copies of itself and other protocols. This relaxation
we consider is simulation in quasi-polynomial (as opposed to
polynomial) time. This relaxation seems to suffice for the
canonical application of multi-party secure computation; that is
obtaining protocols for any task whose privacy, integrity and
input independence cannot broken by efficient adversaries under
reasonable cryptographic assumptions. We emphasize that the
security of our protocol does not rely on setup conditions such
as the existence of a common reference string, nor does it
require an existence of honest majority of parties.

The talk will be self-contained and will not assume prior
knowledge in cryptography.

Joint work with Amit Sahai (UCLA). An extended abstract of this
work will appear in FOCS 2005.