Top

Journal of Cryptology

Published in:

26-04-2019

Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ

Authors: Yehuda Lindell, Benny Pinkas, Nigel P. Smart, Avishay Yanai

Published in: Journal of Cryptology | Issue 3/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of malicious adversaries. This is especially the case in the two-party setting, where constant-round protocols exist that remain fast even over slow networks. However, in the multi-party setting, all concretely efficient fully secure protocols, such as SPDZ, require many rounds of communication. In this paper, we present a constant-round multi-party secure computation protocol that is fully secure in the presence of malicious adversaries and for any number of corrupted parties. Our construction is based on the constant-round protocol of Beaver et al. (the BMR protocol) and is the first version of that protocol that is concretely efficient for the dishonest majority case. Our protocol includes an online phase that is extremely fast and mainly consists of each party locally evaluating a garbled circuit. For the offline phase, we present both a generic construction (using any underlying MPC protocol) and a highly efficient instantiation based on the SPDZ protocol. Our estimates show the protocol to be considerably more efficient than previous fully secure multi-party protocols.

previous article Efficient Fully Structure-Preserving Signatures and Shrinking Commitments

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

In our construction, we use a pseudorandom function as opposed to a pseudorandom generator used in the original BMR [1].

Their original work also offers a version against a malicious adversary; however, it requires an honest majority and is not concretely efficient.

We assume that the parties interact over a point-to-point network.

The external values (as denoted in [2]) are the signals (as denoted in [1]) observable by the parties when evaluating the circuit in the online phase.

Recall that we write our protocol assuming a broadcast channel. Thus, even though we write that in the output stage all parties receive output if \(i=0\), when instantiating the broadcast channel with the simple echo-broadcast described in Sect. 2, some of the honest parties may receive the output and some may abort.

Multiplication (Beaver) triples are a standard part of the implementation of the SPDZ protocol; we assume familiarity with this method in this paper.

By “MPC Engine,” we refer to the underlying secure computation, the SPDZ functionality in this case.

This analysis refers to the complexity of the circuit that the parties garble in the offline phase, not the circuit that the parties wish to compute over their private inputs (i.e., \(C_f\)).

These Random calls are followed immediately with an Open to a party. However, in SPDZ Random followed by Open has roughly the same cost as Random alone.

Note that unlike [29] and other Yao-based techniques we cannot process XOR gates for free. On the other hand, we are not restricted to only two parties.

In this section, we actually refer to the execution in the hybrid model where the parties have access to the underlying MPC functionality. We denote it as real execution for convenience.

Note that the correctness property has shown earlier holds for every input of the honest parties \(x_J\); thus, in order to decide whether to instruct the trusted party to “halt” or “continue” \(\mathcal {S'_{{\text {OUR}}}}\) can just use some fake input \(x_J=0^{|J|}\).

The decision whether to abort or not is not based on whether the adversary cheated or not, but is rather based on the actual evaluation of the circuit because there might be cases where the adversary cheats and influences only the corrupted parties, for example, when cheating in ith PRF values used in a garbled gate of some gate whose output wire is a circuit-output wire (where \(i\in I\)).

D. Beaver, S. Micali, P. Rogaway, The round complexity of secure protocols, in 22nd STOC, pp. 503–513, 1990

A. Ben-David, N. Nisan, B. Pinkas, M. P. Fairplay, A system for secure multi-party computation, in ACM CCS, pp. 257–266, 2008

A. Ben-Efraim, Y. Lindell, E. Omri, Optimizing semi-honest secure multiparty computation for the internet, in ACM CCS, pp. 578–590, 2016

A. Ben-Efraim, Y. Lindell, E. Omri, Efficient scalable constant-round MPC via garbled circuits, in ASIACRYPT, pp. 471–498, 2017

M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in 20th STOC, pp. 1–10, 1988

D. Chaum, C. Crépeau, I. Damgård, Multiparty unconditionally secure protocols, in 20th STOC, pp. 11–19, 1988

S. G. Choi, J. Katz, A. J. Malozemoff, V. Zikas, Efficient three-party computation from cut-and-choose, in CRYPTO, pp. 513–530, 2014

R. Cleve, Limits on the security of coin flips when half the processors are faulty (extended abstract), in 18th STOC, pp. 364–369, 1986

I. Damgård, Y. Ishai, Constant-round multiparty computation using a black-box pseudorandom generator, in CRYPTO, pp. 378–394, 2005

10.

I. Damgård, M. Keller, E. Larraia, C. Miles, N. P. Smart, Implementing AES via an actively/covertly secure dishonest-majority MPC protocol, in SCN, pp. 241–263, 2012

11.

I. Damgård, M. Keller, E. Larraia, V. Pastro, P. Scholl, N. P. Smart, Practical covertly secure MPC for dishonest majority—or: Breaking the SPDZ limits, in ESORICS, pp. 1–18, 2013

12.

I. Damgård, V. Pastro, N. P. Smart, S. Zakarias, Multiparty computation from somewhat homomorphic encryption, in CRYPTO, pp. 643–662, 2012

13.

P. Feldman, S. Micali, An optimal probabilistic protocol for synchronous byzantine agreement. SIAM Journal on Computing 26(4), 873–933 (1997)MathSciNetCrossRefMATH

14.

O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or A completeness theorem for protocols with honest majority, in 19th STOC, pp. 218–229, 1987

15.

S. Goldwasser, Y. Lindell, Secure computation without agreement, in DISC, pp. 17–32, 2002

16.

C. Hazay, P. Scholl, E. Soria-Vazquez, Low cost constant round MPC combining BMR and oblivious transfer, in ASIACRYPT, pp. 598–628, 2017

17.

Y. Ishai, M. Prabhakaran, A. Sahai, Founding cryptography on oblivious transfer—efficiently, in CRYPTO, pp. 572–591, 2008

18.

J. Katz, R. Ostrovsky, A. D. Smith, Round efficiency of multi-party computation with a dishonest majority, in EUROCRYPT, pp. 578–595, 2003

19.

M. Keller, E. Orsini, P. Scholl, MASCOT: faster malicious arithmetic secure computation with oblivious transfer, in ACM CCS, 2016, pp. 830–842, 2016

20.

M. Keller, P. Scholl, N. P. Smart, An architecture for practical actively secure MPC with dishonest majority, in ACM CCS, pp. 549–560, 2013

21.

M. Keller, A. Yanai, Efficient maliciously secure multiparty computation for RAM, in EUROCRYPT, 2018, pp. 91–124, 2018

22.

E. Larraia, E. Orsini, N. P. Smart, Dishonest majority multi-party computation for binary circuits, in CRYPTO, 2014, pp. 495–512, 2014

23.

Y. Lindell, Fast cut-and-choose based protocols for malicious and covert adversaries, in CRYPTO, pp. 1–17, 2013

24.

Y. Lindell, B. Riva, Cut-and-choose yao-based secure computation in the online/offline and batch settings, in CRYPTO, pp. 476–494, 2014

25.

Y. Lindell, N. P. Smart, E. Soria-Vazquez, More efficient constant-round multi-party computation from BMR and SHE, in 14th TCC 2016-B, pp. 554–581, 2016

26.

J. B. Nielsen, P. S. Nordholt, C. Orlandi, S. S. Burra, A new approach to practical active-secure two-party computation, in CRYPTO, pp. 681–700, 2012

27.

R. Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, in 36th STOC, pp. 232–241, 2004

28.

M. C. Pease, R. E. Shostak, L. Lamport, Reaching agreement in the presence of faults. Journal of ACM 27(2), 228–234 (1980)MathSciNetCrossRefMATH

29.

B. Pinkas, T. Schneider, N. P. Smart, S. C. Williams, Secure two-party computation is practical, in ASIACRYPT, pp. 250–267, 2009

30.

T. Rabin, M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, in 21st STOC, pp. 73–85, 1989

31.

P. Rogaway, The round complexity of secure protocols. PhD thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1991

32.

A. C. Yao, Protocols for secure computations, in 23rd FOCS, pp. 160–164, 1982

Title: Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ
Authors: Yehuda Lindell
Benny Pinkas
Nigel P. Smart
Avishay Yanai
Publication date: 26-04-2019
Publisher: Springer US
Published in: Journal of Cryptology / Issue 3/2019
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-019-09322-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2019

Probabilistic Termination and Composability of Cryptographic Protocols

Efficient Fully Structure-Preserving Signatures and Shrinking Commitments

Leakage Resilience from Program Obfuscation

On Black-Box Complexity of Universally Composable Security in the CRS Model

The Magic of ELFs

Beyond Conventional Security in Sponge-Based Authenticated Encryption Modes

Premium Partner