How to Play ANY Mental Game Over the Net
Concurrently composable secure computation without setup
assumptions
Boaz Barak and Amit Sahai
Abstract
We construct a protocol for general multi-party
computation that remains secure even if executed concurrently with
multiple copies of itself and of arbitrary other protocols. This is
the first such construction that is based on standard cryptographic
assumptions and does not require setup conditions such as the
existence of a common reference string. Furthermore, our protocol
utilizes only a constant number of communication rounds and
remains secure also with respect to adaptive adversaries
(without using memory erasures).
The security of our protocol is demonstrated by a simulator with a
quasi-polynomial simulation overhead, as opposed to the
standard notion of polynomial simulation. However, quasi-polynomial
simulation still provides sufficient security for almost all
applications. Furthermore, it was previously shown that there does
not exist such a protocol with polynomial simulation (Lindell, FOCS
'03).
Versions
|