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

Article

Minimising Communication in Honest-Majority MPC by Batchwise Multiplication Verification

Authors:

Peter Sebastian Nordholt,

Meilof VeeningenAuthors Info & Claims

Applied Cryptography and Network Security: 16th International Conference, ACNS 2018, Leuven, Belgium, July 2-4, 2018, Proceedings

Pages 321 - 339

https://doi.org/10.1007/978-3-319-93387-0_17

Published: 02 July 2018 Publication History

Abstract

In this paper, we present two new and very communication-efficient protocols for maliciously secure multi-party computation over fields in the honest-majority setting with abort. Our first protocol improves a recent protocol by Lindell and Nof. Using the so far overlooked tool of batchwise multiplication verification, we speed up their technique for checking correctness of multiplications (with some other improvements), reducing communication by

2 \times

to

7 \times

. In particular, in the 3PC setting, each party sends only two field elements per multiplication. We also show how to achieve fairness, which Lindell and Nof left as an open problem. Our second protocol again applies batchwise multiplication verification, this time to perform 3PC by letting two parties perform the SPDZ protocol using triples generated by a third party and verified batchwise. In this protocol, each party sends only

\frac{4}{3}

field elements during the online phase and

\frac{5}{3}

field elements during the preprocessing phase.

References

[1]

Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: Proceedings of CCS 2016. ACM (2016)

[2]

Ben-Sasson E, Fehr S, and Ostrovsky R Safavi-Naini R and Canetti R Near-linear unconditionally-secure multiparty computation with a dishonest minority Advances in Cryptology – CRYPTO 2012 2012 Heidelberg Springer 663-680

Digital Library

[3]

Canetti R Security and composition of multi-party cryptographic protocols J. Cryptol. 2000 13 1 143-202

Digital Library

[4]

Corrigan-Gibbs, H., Boneh, D.: Prio: private, robust, and scalable computation of aggregate statistics. In: Proceedings of NSDI (2017)

[5]

Damgård I, Keller M, Larraia E, Pastro V, Scholl P, and Smart NP Crampton J, Jajodia S, and Mayes K Practical covertly secure MPC for dishonest majority – or: breaking the SPDZ limits Computer Security – ESORICS 2013 2013 Heidelberg Springer 1-18

[6]

Damgård I and Nielsen JB Menezes A Scalable and unconditionally secure multiparty computation Advances in Cryptology - CRYPTO 2007 2007 Heidelberg Springer 572-590

[7]

Damgård, I., Orlandi, C., Simkin, M.: Yet another compiler for active security or: efficient MPC over arbitrary rings. Cryptology ePrint Archive, Report 2017/908 (2017). http://eprint.iacr.org/2017/908

[8]

Damgård I, Pastro V, Smart N, and Zakarias S Safavi-Naini R and Canetti R Multiparty computation from somewhat homomorphic encryption Advances in Cryptology – CRYPTO 2012 2012 Heidelberg Springer 643-662

Digital Library

[9]

Dolev D and Strong HR Authenticated algorithms for Byzantine agreement SIAM J. Comput. 1983 12 4 656-666

Digital Library

[10]

Fitzi M, Gisin N, Maurer U, and von Rotz O Knudsen LR Unconditional Byzantine agreement and multi-party computation secure against dishonest minorities from scratch Advances in Cryptology—EUROCRYPT 2002 2002 Heidelberg Springer 482-501

[11]

Furukawa J, Lindell Y, Nof A, and Weinstein O Coron J-S and Nielsen JB High-throughput secure three-party computation for malicious adversaries and an honest majority Advances in Cryptology – EUROCRYPT 2017 2017 Cham Springer 225-255

[12]

Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fact-track multiparty computations with applications to threshold cryptography. In: Proceedings of PODC (1998)

[13]

Jakobsen, T.P., Nielsen, J.B., Orlandi, C.: A framework for outsourcing of secure computation. In: Proceedings of CCSW 2014 (2014)

[14]

Keller, M., Pastro, V., Rotaru, D.: Overdrive: making SPDZ great again. Cryptology ePrint Archive, Report 2017/1230 (2017). https://eprint.iacr.org/2017/1230

[15]

Kushilevitz, E., Lindell, Y., Rabin, T.: Information-theoretically secure protocols and security under composition. In: Proceedings of STOC 2006 (2006)

[16]

Lindell, Y., Nof, A.: A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honest-majority. In: Proceedings of CCS 2017. ACM (2017)

[17]

Lipmaa H and Toft T Fomin FV, Freivalds R, Kwiatkowska M, and Peleg D Secure equality and greater-than tests with sublinear online complexity Automata, Languages, and Programming 2013 Heidelberg Springer 645-656

Digital Library

[18]

Mohassel, P., Zhang, Y.: SecureML: a system for scalable privacy-preserving machine learning. In: Proceedings of S&P (2017)

[19]

Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: Proceedings of S&P (2013)

[20]

Schoenmakers B, Veeningen M, and de Vreede N Manulis M, Sadeghi A-R, and Schneider S Trinocchio: privacy-preserving outsourcing by distributed verifiable computation Applied Cryptography and Network Security 2016 Cham Springer 346-366

[21]

Schwartz JT Fast probabilistic algorithms for verification of polynomial identities J. ACM 1980 27 4 701-717

Digital Library

[22]

Zippel R Ng EW Probabilistic algorithms for sparse polynomials Symbolic and Algebraic Computation 1979 Heidelberg Springer 216-226

Cited By

Beck GGoel AHegde AJain AJin ZKaptchuk GMeng WJensen CCremers CKirda E(2023)Scalable Multiparty GarblingProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623132(2158-2172)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623132
Liu HXing CYang YYuan C(2023)Ramp Hyper-invertible Matrices and Their Applications to MPC ProtocolsAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8721-4_7(204-236)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8721-4_7
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
Show More Cited By

Recommendations

Asynchronous MPC with a strict honest majority using non-equivocation
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

Multiparty computation (MPC) among n parties can tolerate up to t < n/2 active corruptions in a synchronous communication setting; however, in an asynchronous communication setting, the resiliency bound decreases to only t < n/3 active corruptions. We ...
Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest
CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted ...
Fast Large-Scale Honest-Majority MPC for Malicious Adversaries
Abstract
Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Applied Cryptography and Network Security: 16th International Conference, ACNS 2018, Leuven, Belgium, July 2-4, 2018, Proceedings

Jul 2018

714 pages

ISBN:978-3-319-93386-3

DOI:10.1007/978-3-319-93387-0

Editors:
Bart Preneel
imec-COSIC, KU Leuven, Heverlee, Belgium
,
Frederik Vercauteren
imec-COSIC, KU Leuven, Heverlee, Belgium

© Springer International Publishing AG, part of Springer Nature 2018.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 02 July 2018

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Beck GGoel AHegde AJain AJin ZKaptchuk GMeng WJensen CCremers CKirda E(2023)Scalable Multiparty GarblingProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623132(2158-2172)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623132
Liu HXing CYang YYuan C(2023)Ramp Hyper-invertible Matrices and Their Applications to MPC ProtocolsAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8721-4_7(204-236)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8721-4_7
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
Goyal VLi HOstrovsky RPolychroniadou ASong Y(2021)ATLAS: Efficient and Scalable MPC in the Honest Majority SettingAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_9(244-274)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-84245-1_9
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
Goyal VPolychroniadou ASong Y(2021)Unconditional Communication-Efficient MPC via Hall’s Marriage TheoremAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_10(275-304)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-84245-1_10
Polychroniadou ASong Y(2021)Constant-Overhead Unconditionally Secure Multiparty Computation Over Binary FieldsAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77886-6_28(812-841)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-77886-6_28
Gordon SStarin DYerukhimovich A(2021)The More the Merrier: Reducing the Cost of Large Scale MPCAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77886-6_24(694-723)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-77886-6_24
Beck GGoel AJain AKaptchuk G(2021)Order-C Secure Multiparty Computation for Highly Repetitive CircuitsAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77886-6_23(663-693)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-77886-6_23
Boyle EGilboa NIshai YNof A(2020)Efficient Fully Secure Computation via Distributed Zero-Knowledge ProofsAdvances in Cryptology – ASIACRYPT 202010.1007/978-3-030-64840-4_9(244-276)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64840-4_9
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten