Welcome to the resource topic for 2005/106
Title:
How To Play Almost Any Mental Game Over The Net — Concurrent Composition via Super-Polynomial Simulation
Authors: Boaz Barak, Amit Sahai
Abstract: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).
ePrint: https://eprint.iacr.org/2005/106
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .