More Web Proxy on the site http://driver.im/

Article

Efficient multi-party computation with dispute control

Authors:

Zuzana Beerliová-Trubíniová,

Martin HirtAuthors Info & Claims

TCC'06: Proceedings of the Third conference on Theory of Cryptography

Pages 305 - 328

https://doi.org/10.1007/11681878_16

Published: 04 March 2006 Publication History

Abstract

Secure multi-party computation (MPC) allows a set of n players to securely compute an agreed function of their inputs, even when up to t players are under the control of an (active or passive) adversary. In the information-theoretic model MPC is possible if and only if t < n/2 (where active security with t ≥ n/3 requires a trusted key setup).

Known passive MPC protocols require a communication of $\mathcal{O}(n^2)$ field elements per multiplication. Recently, the same communication complexity was achieved for active security with t < n/3. It remained an open question whether $\mathcal{O}(n^2)$ complexity is achievable for n/3 ≤ t < n/2.

We answer this question in the affirmative by presenting an active MPC protocol that provides optimal (t < n/2) security and communicates only $\mathcal{O}(n^2)$ field elements per multiplication. Additionally the protocol broadcasts $\mathcal{O}(n^3)$ field elements overall, for the whole computation.

The communication complexity of the new protocol is to be compared with the most efficient previously known protocol for the same model, which requires broadcastingΩ(n⁵) field elements per multiplication. This substantial reduction in communication is mainly achieved by applying a new technique called dispute control: During the course of the protocol, the players keep track of disputes that arise among them, and the ongoing computation is adjusted such that known disputes cannot arise again. Dispute control is inspired by the player-elimination framework. However, player elimination is not suited for models with t ≥ n/3.

References

[1]

D. Beaver. Efficient multiparty protocols using circuit randomization. In CRYPTO '91, LNCS 576, pp. 420-432, 1991.

Digital Library

[2]

D. Beaver. Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology, pp. 75-122, 1991.

[3]

P. Berman, J. A. Garay, and K. J. Perry. Bit optimal distributed consensus. Computer Science Research, pp. 313-322, 1992. Preliminary version in Proc. 21st STOC, 1989.

Digital Library

[4]

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

Digital Library

[5]

D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols (extended abstract). In Proc. 20th STOC, pp. 11-19, 1988.

Digital Library

[6]

R. Cramer, I. Damgård, S. Dziembowski, M. Hirt, and T. Rabin. Efficient multiparty computations secure against an adaptive adversary. In EUROCRYPT '99, LNCS 1592, pp. 311-326, 1999.

Digital Library

[7]

D. Chaum, I. Damgård, and J. van de Graaf. Multiparty computations ensuring privacy of each party's input and correctness of the result. In CRYPTO '87, LNCS 293, pp. 87-119, 1987.

Digital Library

[8]

L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(4):143-154, 1979. Preliminary version in Proc. 9st STOC, 1977.

Digital Library

[9]

B. A. Coan and J. L. Welch. Modular construction of a Byzantine agreement protocol with optimal message bit complexity. Information and Computation, 97(1):61-85, 1992. Preliminary version in Proc. 8th PODC, 1989.

Digital Library

[10]

D. Dolev and H. R. Strong. Polynomial algorithms for multiple processor agreement. In Proc. 14th STOC, pp. 401-407, 1982.

Digital Library

[11]

Z. Galil, S. Haber, and M. Yung. Cryptographic computation: Secure fault-tolerant protocols and the public-key model. In CRYPTO '87, LNCS 293, pp. 135-155, 1987.

Digital Library

[12]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game -- a completeness theorem for protocols with honest majority. In Proc. 19th STOC, pp. 218-229, 1987.

Digital Library

[13]

M. Hirt and U. Maurer. Robustness for free in unconditional multiparty computation. In CRYPTO '01, LNCS 2139, pp. 101-118, 2001.

Digital Library

[14]

M. Hirt, U. Maurer, and B. Przydatek. Efficient secure multi-party computation. In ASIACRYPT '00, LNCS 1976, pp. 143-161, 2000.

Digital Library

[15]

M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, Apr. 1980.

Digital Library

[16]

B. Pfitzmann and M. Waidner. Unconditional Byzantine agreement for any number of faulty processors. In Proc. 9th STACS, LNCS 577, 1992.

Digital Library

[17]

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

Digital Library

[18]

A. Shamir. How to share a secret. Communications of the ACM, 22:612- 613, 1979.

Digital Library

[19]

A. C. Yao. Protocols for secure computations. In Proc. 23rd FOCS, pp. 160-164, 1982.

Digital Library

Cited By

Zhao MQuek TGao DZhou JCardenas A(2024)Honest Majority Multiparty Computation over Rings with Constant Online CommunicationProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3661136(323-335)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3661136
Agarwal ABienstock ADamgård IEscudero D(2024)Honest Majority GOD MPC with Rounds and Low Online CommunicationAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0938-3_8(234-265)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0938-3_8
Song YYe X(2024)Perfectly-Secure MPC with Constant Online Communication ComplexityTheory of Cryptography10.1007/978-3-031-78023-3_11(329-361)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78023-3_11
Show More Cited By

Efficient multi-party computation with dispute control
1. Security and privacy

Recommendations

Efficient Fair Secure Two-Party Computation
APSCC '12: Proceedings of the 2012 IEEE Asia-Pacific Services Computing Conference)

Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called """"garbled circuit"""". Later, many protocols based on garbled circuit approach have been presented, most ...
Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ

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 ...
Efficient two party and multi party computation against covert adversaries
EUROCRYPT'08: Proceedings of the theory and applications of cryptographic techniques 27th annual international conference on Advances in cryptology

Recently, Aumann and Lindell introduced a new realistic security model for secure computation, namely, security against covert adversaries. The main motivation was to obtain secure computation protocols which are efficient enough to be usable in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

TCC'06: Proceedings of the Third conference on Theory of Cryptography

March 2006

616 pages

ISBN:3540327312

Editors:
Shai Halevi
IBM Research, Hawthorne, NY
,
Tal Rabin
IBM T.J.Watson Research Center, Hawthorne, NY

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 04 March 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao MQuek TGao DZhou JCardenas A(2024)Honest Majority Multiparty Computation over Rings with Constant Online CommunicationProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3661136(323-335)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3661136
Agarwal ABienstock ADamgård IEscudero D(2024)Honest Majority GOD MPC with Rounds and Low Online CommunicationAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0938-3_8(234-265)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0938-3_8
Song YYe X(2024)Perfectly-Secure MPC with Constant Online Communication ComplexityTheory of Cryptography10.1007/978-3-031-78023-3_11(329-361)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78023-3_11
Goyal VLiu-Zhang CSong Y(2024)Towards Achieving Asynchronous MPC with Linear Communication and Optimal ResilienceAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_6(170-206)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68397-8_6
Appan AChandramouli AChoudhury A(2023)Perfectly-Secure Synchronous MPC With Asynchronous Fallback GuaranteesIEEE Transactions on Information Theory10.1109/TIT.2023.326444469:8(5386-5425)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3264444
Escudero DFehr S(2023)On Fully-Secure Honest Majority MPC Without Round OverheadProgress in Cryptology – LATINCRYPT 202310.1007/978-3-031-44469-2_3(47-66)Online publication date: 3-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-44469-2_3
Baum CHsin-yu Chiang JDavid BFrederiksen TGentile L(2022)SoK: Mitigation of Front-Running in Decentralized FinanceFinancial Cryptography and Data Security. FC 2022 International Workshops10.1007/978-3-031-32415-4_17(250-271)Online publication date: 6-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-32415-4_17
Dalskov AEscudero D(2021)Honest Majority MPC with Abort with Minimal Online CommunicationProgress in Cryptology – LATINCRYPT 202110.1007/978-3-030-88238-9_22(453-472)Online publication date: 6-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-88238-9_22
Choudhuri AGoel AGreen MJain AKaptchuk G(2021)Fluid MPC: Secure Multiparty Computation with Dynamic ParticipantsAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_4(94-123)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-84245-1_4
Abspoel MDalskov AEscudero DNof A(2021)An Efficient Passive-to-Active Compiler for Honest-Majority MPC over RingsApplied Cryptography and Network Security10.1007/978-3-030-78375-4_6(122-152)Online publication date: 21-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-78375-4_6
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents