Advertisement
Published in:
2008 | OriginalPaper | Chapter
Asynchronous Multi-Party Computation with Quadratic Communication
Authors : Martin Hirt, Jesper Buus Nielsen, Bartosz Przydatek
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present an efficient protocol for secure multi-party computation in the asynchronous model with optimal resilience. For
n
parties, up to
t
<
n
/3 of them being corrupted, and security parameter
κ
, a circuit with
c
gates can be securely computed with communication complexity
$\O(c n^2 \kappa)$
bits, which improves on the previously known solutions by a factor of
Ω
(
n
). The construction of the protocol follows the approach introduced by Franklin and Haber (Crypto’93), based on a public-key encryption scheme with threshold decryption. To achieve the quadratic complexity, we employ several techniques, including circuit randomization due to Beaver (Crypto’91), and an abstraction of
certificates
, which can be of independent interest.