Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We present new and improved protocols for secure multi-party computation. Our main contributions are as follows:

-- a O(log^* n)-round protocol for secure multi-party computation with a dishonest majority 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.

In addition to the results on secure computation, we also obtain a simple, self-contained construction of a O(log^* n)-round non-malleable commitment scheme based on one-way functions, improving upon the recent O(1)^{log^* n} -round protocol of Lin and Pass (STOC 2009). Our construction uses a novel transformation for handling arbitrary man-in-the- middle scheduling strategies which improves upon a previous construction of Barak (FOCS 2002).

Questions and Answers

You need to be logged in to be able to post here.