Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptology
Published in: Journal of Cryptology 4/2020

15-06-2020

Low Cost Constant Round MPC Combining BMR and Oblivious Transfer

Authors: Carmit Hazay, Peter Scholl, Eduardo Soria-Vazquez

Published in: Journal of Cryptology | Issue 4/2020

Log in

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

search-config
loading …

Abstract

In this work, we present two new actively secure, constant-round multi-party computation (MPC) protocols with security against all-but-one corruptions. Our protocols both start with an actively secure MPC protocol, which may have linear round complexity in the depth of the circuit, and compile it into a constant-round protocol based on garbled circuits, with very low overhead.
1.
Our first protocol takes a generic approach using any secret-sharing-based MPC protocol for binary circuits, and a correlated oblivious transfer functionality.
 
2.
Our second protocol builds on secret-sharing-based MPC with information-theoretic MACs. This approach is less flexible, being based on a specific form of MPC, but requires no additional oblivious transfers to compute the garbled circuit.
 
In both approaches, the underlying secret-sharing-based protocol is only used for one actively secure \(\mathbb {F}_2\) multiplication per AND gate. An interesting consequence of this is that, with current techniques, constant-round MPC for binary circuits is not much more expensive than practical, non-constant-round protocols. We demonstrate the practicality of our second protocol with an implementation and perform experiments with up to 9 parties securely computing the AES and SHA-256 circuits. Our running times improve upon the best possible performance with previous protocols in this setting by 60 times.
previous article -Secure Multiparty Computation without an Honest Majority and the Best of Both Worlds
next article Tightly Secure Hierarchical Identity-Based Encryption

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
Appendix
Available only for authorised users
Footnotes
1
Furthermore, the environment sees all of the PRF keys of the honest parties, since these are outputs of the protocol, which seems to rule out any kind of computational reduction in the security proof.
 
2
This is needed to ensure that, for instance, if an output wire w comes from the XOR of two previous AND gates with output wires (u, v), then the public values \(\Lambda _u,\Lambda _v\) are chosen to satisfy \(\Lambda _w = \Lambda _u \oplus \Lambda _v\), as required.
 
3
If counting the total amount of data sent, in both directions, our online cost would be larger than [44], which is highly asymmetric. In practice, however, the latency depends on the largest amount of communication from any one party, which is why we measure in this way.
 
Literature
1.
G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More efficient oblivious transfer extensions with security for malicious adversaries, in Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, (Springer, Heidelberg, April 2015) pp. 673–701.
2.
A. Aly, E. Orsini, D. Rotaru, N.P. Smart, T. Wood. Zaphod: Efficiently combining LSSS and garbled circuits in SCALE, in WAHC’19: Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography. (ACM, 2019). https://​eprint.​iacr.​org/​2019/​974.
3.
E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl. Efficient pseudorandom correlation generators: Silent OT extension and more, in CRYPTO 2019, (2019).
4.
E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, P. Rindal, and P. Scholl. Efficient two-round OT extension and silent non-interactive secure computation, in CCS, (2019) pp. 291–308.
5.
D. Beaver. Efficient multiparty protocols using circuit randomization, in Joan Feigenbaum, editor, CRYPTO’91, volume 576 of LNCS. (Springer, Heidelberg, August 1992), pp. 420–432.
6.
M. Bellare, V.T. Hoang, and P. Rogaway. Foundations of garbled circuits, in Ting Yu, George Danezis, Virgil D. Gligor, editors, ACM CCS 12, . (ACM Press, October 2012) pp. 784–796.
7.
S.S. Burra, E. Larraia, J.B. Nielsen, P.S. Nordholt, C. Orlandi, E. Orsini, P. Scholl, N.P. Smart. High performance multi-party computation for binary circuits based on oblivious transfer. Cryptology ePrint Archive, Report 2015/472, 2015. http://​eprint.​iacr.​org/​2015/​472.
8.
A. Ben-Efraim, Y. Lindell, and E. Omri. Optimizing semi-honest secure multiparty computation for the internet, in Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 16, (ACM Press, October 2016) pp. 578–590.
9.
D. Beaver, S. Micali, P. Rogaway. The round complexity of secure protocols (extended abstract), in 22nd ACM STOC. (ACM Press, May 1990), pp. 503–513.
10.
M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract), in 20th ACM STOC, pp. 1–10. ACM Press, May 1988.
11.
R. Canetti. Universally composable security: A new paradigm for cryptographic protocols, in 42nd FOCS. (IEEE Computer Society Press, October 2001), pp. 136–145.
12.
R. Canetti, A. Cohen, Y. Lindell. A simpler variant of universally composable security for standard multiparty computation, in Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS (Springer, Heidelberg, August 2015), pp. 3–22.
13.
I. Cascudo, I. Damgård, B. David, N. Döttling, J.B. Nielsen. Rate-1, linear time and additively homomorphic UC commitments, in Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS. (Springer, Heidelberg, August 2016), pp. 179–207.
14.
S.G. Choi, J. Katz, R. Kumaresan, H.-S. Zhou. On the security of the “free-XOR” technique, in Ronald Cramer, editor, TCC 2012, volume 7194 of LNCS. (Springer, Heidelberg, March 2012), pp. 39–53.
15.
S.G. Choi, J. Katz, A.J. Malozemoff, V. Zikas. Efficient three-party computation from cut-and-choose, in Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part II, volume 8617 of LNCS. (Springer, Heidelberg, August 2014), pp. 513–530.
16.
I. Damgård, Y. Ishai. Scalable secure multiparty computation, in Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS. (Springer, Heidelberg, August 2006), pp. 501–520.
17.
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 Jason Crampton, Sushil Jajodia, and Keith Mayes, editors, ESORICS 2013, volume 8134 of LNCS. (Springer, Heidelberg, September 2013), pp. 1–18.
18.
I. Damgård, J.B. Nielsen. Scalable and unconditionally secure multiparty computation, in Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS. (Springer, Heidelberg, August 2007), pp. 572–590.
19.
20.
I. Damgård, V. Pastro, N.P. Smart, S. Zakarias. Multiparty computation from somewhat homomorphic encryption, in Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS. (Springer, Heidelberg, August 2012), pp. 643–662.
21.
I. Damgård, S. Zakarias. Constant-overhead secure computation of Boolean circuits using preprocessing, in Amit Sahai, editor, TCC 2013, volume 7785 of LNCS. (Springer, Heidelberg, March 2013), pp. 621–641.
22.
T.K. Frederiksen, M. Keller, E. Orsini, P. Scholl. A unified approach to MPC with preprocessing using OT, in Tetsu Iwata and Jung Hee Cheon, editors, ASIACRYPT 2015, Part I, volume 9452 of LNCS. (Springer, Heidelberg, November / December 2015), pp. 711–735.
23.
J. Furukawa, Y. Lindell, A. Nof, O. Weinstein. High-throughput secure three-party computation for malicious adversaries and an honest majority, in EUROCRYPT, (2017), pp. 225–255.
24.
T.K. Frederiksen, B. Pinkas, A. Yanai. Committed MPC - maliciously secure multiparty computation from homomorphic commitments, in Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 25-29, 2018, Proceedings, Part I, pp. 587–619, (2018).
25.
S. Goldwasser, Y. Lindell. Secure multi-party computation without agreement. Journal of Cryptology, 18(3):247–287, (2005).MathSciNetCrossRef
26.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority, in Alfred Aho, editor, 19th ACM STOC. (ACM Press, May 1987), pp. 218–229.
27.
Y. Ishai, M. Prabhakaran, A. Sahai. Founding cryptography on oblivious transfer - efficiently, in David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS. (Springer, Heidelberg, August 2008), pp. 572–591.
28.
Y. Ishai, M. Prabhakaran, A. Sahai. Secure arithmetic computation with no honest majority, in Omer Reingold, editor, TCC 2009, volume 5444 of LNCS. (Springer, Heidelberg, March 2009), pp. 294–314.
29.
M. Keller, E. Orsini, P. Scholl. MASCOT: Faster malicious arithmetic secure computation with oblivious transfer, in Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 16. (ACM Press, October 2016), pp. 830–842.
30.
31.
V. Kolesnikov, T. Schneider. Improved garbled circuit: Free XOR gates and applications, in Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, ICALP 2008, Part II, volume 5126 of LNCS, pp. 486–498. (Springer, Heidelberg, July 2008).
32.
Y. Lindell, B. Pinkas. An efficient protocol for secure two-party computation in the presence of malicious adversaries, in Moni Naor, editor, EUROCRYPT 2007, volume 4515 of LNCS. (Springer, Heidelberg, May 2007), pp. 52–78.
33.
Y. Lindell and B. Pinkas. A proof of security of Yao’s protocol for two-party computation. Journal of Cryptology, 22(2):161–188, (2009).MathSciNetCrossRef
34.
Y. Lindell, B. Pinkas. Secure two-party computation via cut-and-choose oblivious transfer, in Yuval Ishai, editor, TCC 2011, volume 6597 of LNCS. (Springer, Heidelberg, March 2011), pp. 329–346.
35.
Y. Lindell, B. Pinkas, N.P. Smart, A. Yanai. Efficient constant round multi-party computation combining BMR and SPDZ, in Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS. (Springer, Heidelberg, August 2015), pp. 319–338.
36.
Y. Lindell, B. Riva. Blazing fast 2PC in the offline/online setting with security for malicious adversaries, in Indrajit Ray, Ninghui Li, and Christopher Kruegel:, editors, ACM CCS 15. (ACM Press, October 2015), pp. 579–590.
37.
Y. Lindell, N.P. Smart, Eduardo Soria-Vazquez. More efficient constant-round multi-party computation from BMR and SHE, in Martin Hirt and Adam D. Smith, editors, TCC 2016-B, Part I, volume 9985 of LNCS. (Springer, Heidelberg, October / November 2016), pp. 554–581.
38.
P. Mohassel, M. Rosulek, Y. Zhang. Fast and secure three-party computation: The garbled circuit approach, in Indrajit Ray, Ninghui Li, and Christopher Kruegel:, editors, ACM CCS 15. (ACM Press, October 2015), pp. 591–602.
39.
J.B. Nielsen, P.S. Nordholt, C. Orlandi, S.S. Burra. A new approach to practical active-secure two-party computation, in Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS. (Springer, Heidelberg, August 2012), pp. 681–700.
40.
41.
T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract), in 21st ACM STOC, pp. 73–85. ACM Press, May 1989.
42.
43.
P. Rindal and M. Rosulek. Faster malicious 2-party secure computation with online/offline dual execution, in USENIX, pp. 297–314, 2016.
44.
X. Wang, S. Ranellucci, and J. Katz. Authenticated garbling and efficient maliciously secure two-party computation, in CCS, pp. 21–37, 2017.
45.
X. Wang, S. Ranellucci, and J. Katz. Global-scale secure multiparty computation, in CCS, pp. 39–56, 2017.
46.
A.C.-C. Yao. How to generate and exchange secrets (extended abstract), in 27th FOCS, pp. 162–167. IEEE Computer Society Press, October 1986.
47.
Metadata
Title
Low Cost Constant Round MPC Combining BMR and Oblivious Transfer
Authors
Carmit Hazay
Peter Scholl
Eduardo Soria-Vazquez
Publication date
15-06-2020
Publisher
Springer US
Published in
Journal of Cryptology / Issue 4/2020
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-020-09355-y

Other articles of this Issue 4/2020

Journal of Cryptology 4/2020 Go to the issue

OriginalPaper

A Formal Security Analysis of the Signal Messaging Protocol

OriginalPaper

Non-malleable Encryption: Simpler, Shorter, Stronger

OriginalPaper

Continuously Non-malleable Codes in the Split-State Model

OriginalPaper

-Secure Multiparty Computation without an Honest Majority and the Best of Both Worlds

OriginalPaper

Adaptively Secure Non-interactive CCA-Secure Threshold Cryptosystems: Generic Framework and Constructions

OriginalPaper

The IITM Model: A Simple and Expressive Model for Universal Composability

Premium Partner

    Image Credits