Efficient multiparty protocols via log-depth threshold formulae (Extended abstract)

Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

We put forward a new approach for the design of efficient multiparty protocols: 1. Design a protocol π for a small number of parties (say, 3 or 4) which achieves security against a single corrupted party. Such protocols are typically easy to construct, as they may employ techniques that do not scale well with the number of corrupted parties. 2. Recursively compose π with itself to obtain an efficient n-party protocol which achieves security against a constant fraction of corrupted parties. The second step of our approach combines the "player emulation" technique of Hirt and Maurer (J. Cryptology, 2000) with constructions of logarithmic-depth formulae which compute threshold functions using only constant fan-in threshold gates. Using this approach, we simplify and improve on previous results in cryptography and distributed computing. In particular: - We provide conceptually simple constructions of efficient protocols for Secure Multiparty Computation (MPC) in the presence of an honest majority, as well as broadcast protocols from point-to-point channels and a 2-cast primitive. - We obtain new results on MPC over blackbox groups and other algebraic structures. The above results rely on the following complexity-theoretic contributions, which may be of independent interest: - We show that for every j,k ∈ ℕ such that m Delta equal to k-1/j-1 is an integer, there is an explicit (poly(n)-time) construction of a logarithmic-depth formula which computes a good approximation of an (n/m)-out-of-n threshold function using only j-out-of-k threshold gates and no constants. For the special case of n-bit majority from 3-bit majority gates, a non-explicit construction follows from the work of Valiant (J. Algorithms, 1984). - For this special case, we provide an explicit construction with a better approximation than for the general threshold case, and also an exact explicit construction based on standard complexity-theoretic or cryptographic assumptions.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology, CRYPTO 2013 - 33rd Annual Cryptology Conference, Proceedings
Pages185-202
Number of pages18
EditionPART 2
DOIs
StatePublished - Sep 26 2013
Event33rd Annual International Cryptology Conference, CRYPTO 2013 - Santa Barbara, CA, United States
Duration: Aug 18 2013Aug 22 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume8043 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other33rd Annual International Cryptology Conference, CRYPTO 2013
CountryUnited States
CitySanta Barbara, CA
Period8/18/138/22/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficient multiparty protocols via log-depth threshold formulae (Extended abstract)'. Together they form a unique fingerprint.

  • Cite this

    Cohen, G., Damgård, I. B., Ishai, Y., Kölker, J., Miltersen, P. B., Raz, R., & Rothblum, R. D. (2013). Efficient multiparty protocols via log-depth threshold formulae (Extended abstract). In Advances in Cryptology, CRYPTO 2013 - 33rd Annual Cryptology Conference, Proceedings (PART 2 ed., pp. 185-202). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8043 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-40084-1_11