nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

From Fairness to Full Security in Multiparty Computation

verfasst von : Ran Cohen, Iftach Haitner, Eran Omri, Lior Rotem

Erschienen in: Security and Cryptography for Networks

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In the setting of secure multiparty computation (MPC), a set of mutually distrusting parties wish to jointly compute a function in a correct and private manner. An MPC protocol is called fully secure if no adversary can prevent the honest parties from obtaining their outputs. A protocol is called fair if an adversary can prematurely abort the computation, however, only before learning any new information.

We present highly efficient transformations from fair computations to fully secure computations, assuming the fraction of honest parties is constant (e.g., \(1\%\) of the parties are honest). Compared to previous transformations that require linear invocations (in the number of parties) of the fair computation, our transformations require super-logarithmic, and sometimes even super-constant, such invocations.

One application of these transformations is a new \(\delta \)-bias coin-flipping protocol, whose round complexity has a super-logarithmic dependency on the number of parties, improving over the protocol of Beimel, Omri, and Orlov (Crypto 2010) that has a linear dependency. A second application is a new fully secure protocol for computing the Boolean OR function, with a super-constant round complexity, improving over the protocol of Gordon and Katz (TCC 2009) whose round complexity is linear in the number of parties.

Finally, we show that our positive results are in a sense optimal, by proving that for some functionalities, a super-constant number of (sequential) invocations of the fair computation is necessary for computing the functionality in a fully secure manner.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Proactive Secure Multiparty Computation with a Dishonest Majority

Nächstes Kapitel Efficient Scalable Multiparty Private Set-Intersection via Garbled Bloom Filters

This property is also known as guaranteed output delivery.

A \((t+1)\)-out-of-n secret-sharing scheme is error correcting, if the reconstruction algorithm outputs the correct secret even when up to t shares are arbitrarily modified. ECSS schemes are also known as robust secret sharing.

Same as security with abort, except that upon a premature abort, all honest parties identify a corrupted party.

Unless stated otherwise, we assume that parties can communicate over a broadcast channel. If a broadcast channel is not available, identifiable abort cannot be achieved generically [6], and indeed, some functionalities can be fairly computed, but not with full security [6, 7].

Following [15], by a black-box access to a protocol we mean a black-box usage of a semi-honest MPC protocol computing its next-message function.

Private messages should be encrypted before being sent over the broadcast channel.

In the with-input setting Sect. 2.1, the adversary also obtains the input values of all honest parties.

The attacker of [5] either aborts at round \(i^*\) or at round \(i^*+1\), but the transformation to the above attacker is simple (see the full version [8]).

Although non-interactive perfectly binding commitments can be constructed from one-way permutations, in our setting, one-way functions are sufficient. This follows since Naor’s commitments [21] can be made non-interactive in the common random string (CRS) model, and even given a weak CRS (a high min-entropy common string). A high min-entropy string can be constructed by n parties, without assuming an honest majority, using the protocol from [12] that requires \(log^*(n)+O(1)\) rounds.

t-full-privacy means that the adversary does not learn any additional information other than what it can learn from \(t+1\) invocations of the ideal functionality, with fixed inputs for the honest parties.

A computation has \(\alpha \)-partially identifiable abort [18], if in case the adversary aborts the computation, a subset of parties is identified, such that at least an \(\alpha \)-fraction of the subset is corrupted.

By \(\varphi =1/\sqrt{1-2\beta '}+\varOmega (1)\) we mean that for sufficiently large \(\kappa \) it holds that \(\varphi (\kappa )>1/\sqrt{1-2\beta '}\).

Alon, B., Omri, E.: Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious. In: Hirt, M., Smith, A. (eds.) TCC 2016 Part I. LNCS, vol. 9985, pp. 307–335. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53641-4_13CrossRef

Averbuch, B., Blum, M., Chor, B., Goldwasser, S., Micali, S.: How to implement Bracha’s \({O}(\log n)\) Byzantine agreement algorithm (1985). Unpublished manuscript

Beimel, A., Omri, E., Orlov, I.: Protocols for multiparty coin toss with a dishonest majority. JCRYPTOL 28(3), 551–600 (2015)MathSciNetMATH

Buchbinder, N., Haitner, I., Levi, N., Tsfadia, E.: Fair coin flipping: tighter analysis and the many-party case. In: SODA, pp. 2580–2600 (2017)

Cleve, R.: Limits on the security of coin flips when half the processors are faulty. In: STOC, pp. 364–369 (1986)

Cohen, R., Lindell, Y.: Fairness versus guaranteed output delivery in secure multiparty computation. JCRYPTOL 30(4), 1157–1186 (2017)MathSciNetMATH

Cohen, R., Haitner, I., Omri, E., Rotem, L.: Characterization of secure multiparty computation without broadcast. JCRYPTOL 31(2), 587–609 (2018)MathSciNetMATH

Cohen, R., Haitner, I., Omri, E., Rotem, L.: From fairness to full security in multiparty computation. Manuscript (2018)

Feige, U.: Noncryptographic selection protocols. In: FOCS, pp. 142–153 (1999)

10.

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

11.

Gordon, S.D., Katz, J.: Complete fairness in multi-party computation without an honest majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 19–35. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_2CrossRef

12.

Gradwohl, R., Vadhan, S.P., Zuckerman, D.: Random selection with an adversarial majority. In: CRYPTO 2006, pp. 409–426 (2006)

13.

Haitner, I., Tsfadia, E.: An almost-optimally fair three-party coin-flipping protocol. In: STOC, pp. 817–836 (2014)

14.

Hazay, C., Lindell, Y.: Efficient Secure Two-Party Protocols - Techniques and Constructions. Information Security and Cryptography. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14303-8CrossRefMATH

15.

Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: STOC, pp. 21–30 (2007)

16.

Ishai, Y., Katz, J., Kushilevitz, E., Lindell, Y., Petrank, E.: On achieving the “best of both worlds” in secure multiparty computation. SICOMP 40(1), 122–141 (2011)MathSciNetCrossRef

17.

Ishai, Y., Ostrovsky, R., Zikas, V.: Secure multi-party computation with identifiable abort. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014 Part II. LNCS, vol. 8617, pp. 369–386. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_21CrossRef

18.

Ishai, Y., Kushilevitz, E., Prabhakaran, M., Sahai, A., Yu, C.-H.: Secure protocol transformations. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016 Part II. LNCS, vol. 9815, pp. 430–458. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_15CrossRef

19.

Makriyannis, N.: On the classification of finite Boolean functions up to fairness. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 135–154. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10879-7_9CrossRef

20.

Moran, T., Naor, M., Segev, G.: An optimally fair coin toss. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 1–18. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_1CrossRef

21.

Naor, M.: Bit commitment using pseudorandomness. JCRYPTOL 4(2), 151–158 (1991). Preliminary version in CRYPTO ’89MATH

22.

Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: STOC, pp. 232–241 (2004)

Titel: From Fairness to Full Security in Multiparty Computation
verfasst von: Ran Cohen
Iftach Haitner
Eran Omri
Lior Rotem
Verlag: Springer International Publishing
Buch: Security and Cryptography for Networks
Print ISBN: 978-3-319-98112-3

Electronic ISBN: 978-3-319-98113-0

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-98113-0_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner