×

Scalable multiparty computation with nearly optimal work and resilience. (English) Zbl 1183.68082

Wagner, David (ed.), Advances in cryptology – CRYPTO 2008. 28th annual international cryptology conference, Santa Barbara, CA, USA, August 17–21, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85173-8/pbk). Lecture Notes in Computer Science 5157, 241-261 (2008).
Summary: We present the first general protocol for secure multiparty computation in which the total amount of work required by \(n\) players to compute a function \(f\) grows only polylogarithmically with \(n\) (ignoring an additive term that depends on \(n\) but not on the complexity of \(f)\). Moreover, the protocol is also nearly optimal in terms of resilience, providing computational security against an active, adaptive adversary corrupting a \((1/2 - \epsilon )\) fraction of the players, for an arbitrary \(\epsilon > 0\).
For the entire collection see [Zbl 1155.94010].

MSC:

68M12 Network protocols
68M14 Distributed systems
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI