Article

Two-Round Adaptively Secure Multiparty Computation from Standard Assumptions

Authors:

Fabrice Benhamouda,

Antigoni Polychroniadou,

Muthuramakrishnan VenkitasubramaniamAuthors Info & Claims

Theory of Cryptography: 16th International Conference, TCC 2018, Panaji, India, November 11–14, 2018, Proceedings, Part I

Pages 175 - 205

https://doi.org/10.1007/978-3-030-03807-6_7

Published: 11 November 2018 Publication History

Abstract

We present the first two-round multiparty computation (MPC) protocols secure against malicious adaptive corruption in the common reference string (CRS) model, based on DDH, LWE, or QR. Prior two-round adaptively secure protocols were known only in the two-party setting against semi-honest adversaries, or in the general multiparty setting assuming the existence of indistinguishability obfuscation (iO).

Our protocols are constructed in two steps. First, we construct two-round oblivious transfer (OT) protocols secure against malicious adaptive corruption in the CRS model based on DDH, LWE, or QR. We achieve this by generically transforming any two-round OT that is only secure against static corruption but has certain oblivious sampleability properties, into a two-round adaptively secure OT. Prior constructions were only secure against semi-honest adversaries or based on iO.

Second, building upon recent constructions of two-round MPC from two-round OT in the weaker static corruption setting [Garg and Srinivasan, Benhamouda and Lin, Eurocrypt’18] and using equivocal garbled circuits from [Canetti, Poburinnaya and Venkitasubramaniam, STOC’17], we show how to construct two-round adaptively secure MPC from two-round adaptively secure OT and constant-round adaptively secure MPC, with respect to both malicious and semi-honest adversaries. As a corollary, we also obtain the first 2-round MPC secure against semi-honest adaptive corruption in the plain model based on augmented non-committing encryption (NCE), which can be based on a variety of assumptions, CDH, RSA, DDH, LWE, or factoring Blum integers. Finally, we mention that our OT and MPC protocols in the CRS model are, in fact, adaptively secure in the Universal Composability framework.

References

[1]

Abdalla M, Benhamouda F, and Pointcheval D Fehr S Removing erasures with explainable hash proof systems Public-Key Cryptography – PKC 2017 2017 Heidelberg Springer 151-174

[2]

Asharov G, Jain A, López-Alt A, Tromer E, Vaikuntanathan V, and Wichs D Pointcheval D and Johansson T Multiparty computation with low communication, computation and interaction via threshold FHE Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 483-501

[3]

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th ACM STOC, pp. 1–10. ACM Press, May 1988

[4]

Benhamouda F, Blazy O, Ducas L, and Quach W Abdalla M and Dahab R Hash proof systems over lattices revisited Public-Key Cryptography – PKC 2018 2018 Cham Springer 644-674

[5]

Benhamouda F and Lin H Nielsen JB and Rijmen V k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 500-532

[6]

Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 16, pp. 1292–1303. ACM Press, October 2016

[7]

Boyle E, Gilboa N, and Ishai Y Coron J-S and Nielsen JB Group-based secure computation: optimizing rounds, communication, and computation Advances in Cryptology – EUROCRYPT 2017 2017 Cham Springer 163-193

[8]

Boyle, E., Gilboa, N., Ishai, Y., Lin, H., Tessaro, S.: Foundations of homomorphic secret sharing. In: ITCS (2018, to appear)

[9]

Brakerski Z and Perlman R Robshaw M and Katz J Lattice-based fully dynamic multi-key FHE with short ciphertexts Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 190-213

[10]

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press, October 2001

[11]

Canetti R, Dodis Y, Pass R, and Walfish S Vadhan SP Universally composable security with global setup Theory of Cryptography 2007 Heidelberg Springer 61-85

[12]

Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: 28th ACM STOC, pp. 639–648. ACM Press, May 1996

[13]

Canetti R and Fischlin M Kilian J Universally composable commitments Advances in Cryptology — CRYPTO 2001 2001 Heidelberg Springer 19-40

[14]

Canetti R, Goldwasser S, and Poburinnaya O Dodis Y and Nielsen JB Adaptively secure two-party computation from indistinguishability obfuscation Theory of Cryptography 2015 Heidelberg Springer 557-585

[15]

Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: 34th ACM STOC, pp. 494–503. ACM Press, May 2002

[16]

Canetti R, Poburinnaya O, and Venkitasubramaniam M Fehr S Better two-round adaptive multi-party computation Public-Key Cryptography – PKC 2017 2017 Heidelberg Springer 396-427

[17]

Canetti, R., Poburinnaya, O., Venkitasubramaniam, M.: Equivocating yao: constant-round adaptively secure multiparty computation in the plain model. In: Hatami, H., McKenzie, P., King, V. (eds.) 49th ACM STOC, pp. 497–509. ACM Press, June 2017

[18]

Choi SG, Dachman-Soled D, Malkin T, and Wee H Matsui M Improved non-committing encryption with applications to adaptively secure protocols Advances in Cryptology – ASIACRYPT 2009 2009 Heidelberg Springer 287-302

[19]

Choi SG, Katz J, Wee H, and Zhou H-S Kurosawa K and Hanaoka G Efficient, adaptively secure, and composable oblivious transfer with a single, global CRS Public-Key Cryptography – PKC 2013 2013 Heidelberg Springer 73-88

[20]

Clear M and McGoldrick C Gennaro R and Robshaw M Multi-identity and multi-key leveled FHE from learning with errors Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 630-656

[21]

Cramer R and Shoup V Knudsen LR Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption Advances in Cryptology — EUROCRYPT 2002 2002 Heidelberg Springer 45-64

[22]

Dachman-Soled D, Katz J, and Rao V Dodis Y and Nielsen JB Adaptively secure, universally composable, multiparty computation in constant rounds Theory of Cryptography 2015 Heidelberg Springer 586-613

[23]

Damgård I, Polychroniadou A, and Rao V Cheng C-M, Chung K-M, Persiano G, and Yang B-Y Adaptively secure multi-party computation from LWE (via equivocal FHE) Public-Key Cryptography – PKC 2016 2016 Heidelberg Springer 208-233

[24]

Garay JA, Wichs D, and Zhou H-S Halevi S Somewhat non-committing encryption and efficient adaptively secure oblivious transfer Advances in Cryptology - CRYPTO 2009 2009 Heidelberg Springer 505-523

[25]

Garg S, Gentry C, Halevi S, and Raykova M Lindell Y Two-round secure MPC from indistinguishability obfuscation Theory of Cryptography 2014 Heidelberg Springer 74-94

[26]

Garg S and Polychroniadou A Dodis Y and Nielsen JB Two-round adaptively secure MPC from indistinguishability obfuscation Theory of Cryptography 2015 Heidelberg Springer 614-637

[27]

Garg, S., Srinivasan, A.: Garbled protocols and two-round MPC from bilinear maps. In: 58th FOCS, pp. 588–599. IEEE Computer Society Press (2017)

[28]

Garg S and Srinivasan A Nielsen JB and Rijmen V Two-round multiparty secure computation from minimal assumptions Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 468-499

[29]

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pp. 218–229. ACM Press, May 1987

[30]

Goldwasser S and Micali S Probabilistic encryption J. Comput. Syst. Sci. 1984 28 2 270-299

[31]

Dov Gordon S, Liu F-H, and Shi E Gennaro R and Robshaw M Constant-round MPC with fairness and guarantee of output delivery Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 63-82

[32]

Halevi S and Kalai YT Smooth projective hashing and two-message oblivious transfer J. Cryptol. 2012 25 1 158-193

[33]

Hofheinz D and Kiltz E Halevi S The group of signed quadratic residues and applications Advances in Cryptology - CRYPTO 2009 2009 Heidelberg Springer 637-653

[34]

Mukherjee P and Wichs D Fischlin M and Coron J-S Two round multiparty computation via multi-key FHE Advances in Cryptology – EUROCRYPT 2016 2016 Heidelberg Springer 735-763

[35]

Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Kosaraju, S.R. (ed.) 12th SODA, pp. 448–457. ACM-SIAM, January 2001

[36]

Peikert C and Shiehian S Hirt M and Smith A Multi-key FHE from LWE, revisited Theory of Cryptography 2016 Heidelberg Springer 217-238

[37]

Peikert C, Vaikuntanathan V, and Waters B Wagner D A framework for efficient and composable oblivious transfer Advances in Cryptology – CRYPTO 2008 2008 Heidelberg Springer 554-571

[38]

Yao, A.C.C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd FOCS, pp. 80–91. IEEE Computer Society Press, November 1982

Cited By

Morgan APass R(2022)Concurrently Composable Non-interactive Secure ComputationAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22963-3_18(526-555)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-22963-3_18
Lin HLiu T(2022)Two-Round MPC Without Round Collapsing Revisited – Towards Efficient Malicious ProtocolsAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_13(353-382)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15802-5_13
Bangalore LOstrovsky RPoburinnaya OVenkitasubramaniam M(2022)Adaptively Secure Computation for RAM ProgramsAdvances in Cryptology – EUROCRYPT 202210.1007/978-3-031-07085-3_7(187-216)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-07085-3_7
Show More Cited By

Index Terms

Two-Round Adaptively Secure Multiparty Computation from Standard Assumptions
1. Security and privacy
  1. Cryptography
2. Theory of computation
  1. Computational complexity and cryptography

Index terms have been assigned to the content through auto-classification.

Recommendations

Two-Round MPC: Information-Theoretic and Black-Box
Theory of Cryptography
Abstract
We continue the study of protocols for secure multiparty computation (MPC) that require only two rounds of interaction. The recent works of Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) essentially settle the ...
Round-Optimal Secure Multiparty Computation with Honest Majority
Advances in Cryptology – CRYPTO 2018
Abstract
We study the exact round complexity of secure multiparty computation (MPC) in the honest majority setting. We construct several round-optimaln-party protocols, tolerating any corruptions.
1. Security with abort: We give the first construction of two ...
Two-round Multiparty Secure Computation from Minimal Assumptions
We provide new two-round multiparty secure computation (MPC) protocols in the dishonest majority setting assuming the minimal assumption that two-round oblivious transfer (OT) exists. If the assumed two-round OT protocol is secure against semi-honest ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Theory of Cryptography: 16th International Conference, TCC 2018, Panaji, India, November 11–14, 2018, Proceedings, Part I

Nov 2018

700 pages

ISBN:978-3-030-03806-9

DOI:10.1007/978-3-030-03807-6

Editors:
Amos Beimel
Ben Gurion University, Beer Sheva, Israel
,
Stefan Dziembowski
University of Warsaw, Warsaw, Poland

© International Association for Cryptologic Research 2018.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 11 November 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Morgan APass R(2022)Concurrently Composable Non-interactive Secure ComputationAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22963-3_18(526-555)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-22963-3_18
Lin HLiu T(2022)Two-Round MPC Without Round Collapsing Revisited – Towards Efficient Malicious ProtocolsAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_13(353-382)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15802-5_13
Bangalore LOstrovsky RPoburinnaya OVenkitasubramaniam M(2022)Adaptively Secure Computation for RAM ProgramsAdvances in Cryptology – EUROCRYPT 202210.1007/978-3-031-07085-3_7(187-216)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-07085-3_7
Chakraborty SGanesh CPancholi MSarkar P(2021)Reverse Firewalls for Adaptively Secure MPC Without SetupAdvances in Cryptology – ASIACRYPT 202110.1007/978-3-030-92075-3_12(335-364)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-92075-3_12
Alamati NMontgomery HPatranabis SSarkar P(2021)Two-Round Adaptively Secure MPC from Isogenies, LPN, or CDHAdvances in Cryptology – ASIACRYPT 202110.1007/978-3-030-92075-3_11(305-334)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-92075-3_11
Hirt MLiu-Zhang CMaurer U(2021)Adaptive Security of Multi-party Protocols, RevisitedTheory of Cryptography10.1007/978-3-030-90459-3_23(686-716)Online publication date: 8-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-90459-3_23
Canetti RSarkar PWang X(2020)Efficient and Round-Optimal Oblivious Transfer and Commitment with Adaptive SecurityAdvances in Cryptology – ASIACRYPT 202010.1007/978-3-030-64840-4_10(277-308)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64840-4_10
Lin HLiu TWee H(2020)Information-Theoretic 2-Round MPC Without Round Collapsing: Adaptive Security, and MoreTheory of Cryptography10.1007/978-3-030-64378-2_18(502-531)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64378-2_18
Alon BOmri EPaskin-Cherniavsky A(2020)MPC with Friends and FoesAdvances in Cryptology – CRYPTO 202010.1007/978-3-030-56880-1_24(677-706)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-56880-1_24
Cohen RGaray JZikas V(2020)Broadcast-Optimal Two-Round MPCAdvances in Cryptology – EUROCRYPT 202010.1007/978-3-030-45724-2_28(828-858)Online publication date: 10-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-45724-2_28
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents