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

Springer Science and Business Media LLC - Tập 32 - Trang 1026-1069 - 2019
Yehuda Lindell1, Benny Pinkas2, Nigel P. Smart3,4, Avishay Yanai2
1Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel
2Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel.
3Department of Computer Science, University of Bristol, Bristol, UK
4imec-COSIC, KU Leuven, Leuven, Belgium

Tóm tắt

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.

Tài liệu tham khảo

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 32

1026-1069

Thông tin tác giả