Black-Box, Round-Efficient Secure Computation via Non-Malleability Amplification
Speaker: Hoeteck Wee , U.C. Berkeley
Date: November 19 2010
Time: 10:30AM to 12:00PM
Location: 32-G449 Patil/Kiva
Host: Shafi Goldwasser, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
We present round-efficient protocols for secure multi-party
computation with a dishonest majority that rely on *black-box*
access to the underlying primitives. Our main contributions are:
-- a O(log^* n)-round protocol that relies on black-box access to
dense cryptosystems, homomorphic encryption schemes, or lossy
encryption schemes. This improves upon the recent O(1)^{log^* n}
-round protocol of Lin, Pass and Venkitasubramaniam (STOC 2009)
that relies on non-black-box access to a smaller class of
primitives.
-- a O(1)-round protocol requiring in addition, black-box access
to a one-way function with sub-exponential hardness, improving
upon the recent work of Pass and Wee (Eurocrypt 2010).
These are the first black-box constructions for secure computation
with sublinear round complexity. Our constructions build on and
improve upon the work of Lin and Pass (STOC 2009) on non-malleability
amplification, as well as that of Ishai et al. (STOC 2006) on
black-box secure computation.
See other events that are part of CIS Seminars 2010/2011
See other events happening in November 2010
