Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Nonlinear Invariant Attack Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Constant-Round Asynchronous Multi-Party Computation Based on One-Way Functions

verfasst von : Sandro Coretti, Juan Garay, Martin Hirt, Vassilis Zikas

Erschienen in: Advances in Cryptology – ASIACRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

Secure multi-party computation (MPC) allows several mutually distrustful parties to securely compute a joint function of their inputs and exists in two main variants: In synchronous MPC parties are connected by a synchronous network with a global clock, and protocols proceed in rounds with strong delivery guarantees, whereas asynchronous MPC protocols can be deployed even in networks that deliver messages in an arbitrary order and impose arbitrary delays on them.
The two models—synchronous and asynchronous—have to a large extent developed in parallel with results on both feasibility and asymptotic efficiency improvements in either track. The most notable gap in this parallel development is with respect to round complexity. In particular, although under standard assumptions on a synchronous communication network (availability of secure channels and broadcast), synchronous MPC protocols with (exact) constant rounds have been constructed, to the best of our knowledge, thus far no constant-round asynchronous MPC protocols based on standard assumptions are known, with the best protocols requiring a number of rounds that is linear in the multiplicative depth of the arithmetic circuit computing the desired function.
In this work we close this gap by providing the first constant-round asynchronous MPC protocol that is optimally resilient (i.e., it tolerates up to \(t<n/3\) corrupted parties), adaptively secure, and makes black-box use of a pseudo-random function. It works under the standard network assumptions for protocols in the asynchronous MPC setting, namely, a complete network of point-to-point (secure) asynchronous channels with eventual delivery and asynchronous Byzantine agreement (aka consensus). We provide formal definitions of these primitives and a proof of security in the Universal Composability framework.

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 How to Circumvent the Two-Ciphertext Lower Bound for Linear Garbling Schemes
Nächstes Kapitel Reactive Garbling: Foundation, Instantiation, Application
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The eventual-delivery assumption is supported by the fact that whenever a message is dropped or delayed for too long, Internet protocols typically resend that message.
 
2
What “enough” means is concretely specified by the party’s protocol.
 
3
This speed up, however, does not come for free, as it inevitably allows the adversary to exclude some of the honest parties’ inputs from being considered in the computation.
 
4
Note that while the UC framework already is asynchronous, asynchronous communication with eventual delivery has not been modeled in it so far; moreover, standard (asynchronous) UC protocols do not achieve achieve eventual termination/delivery (cf. Sect. 3).
 
5
An approach based on threshold fully homomorphic encryption was recently proposed by Cohen [17]; see the discussion in the related work section below.
 
6
The necessity of this bound in the asynchronous setting is also discussed in related work below.
 
7
The necessity of the \(t<n/3\) bound follows from the result by Canetti et al. [5, 12], who argue that this bound is necessary for fail-stop adversaries; it also applies to computational security and assuming A-BA. Moreover, note that in the asynchronous setting, all feasibility bounds are worse by an additive term of t compared to the synchronous setting. Intuitively, this stems from the fact that honest parties cannot distinguish between messages by other honest parties being delayed and messages by corrupted parties not being sent. Thus, in particular, perfectly secure asynchronous MPC is possible only if \(t < n/4\).
 
8
Nonetheless, [6] does describe an alternative way of obtaining several asynchronous BA protocols that are guaranteed to all terminate in expected constant number of rounds.
 
9
[8] also assumes A-Cast to get a more efficient solution, but as argued in the introduction, A-Cast can be easily reduced to asynchronous BA in two rounds.
 
10
Note that in each such round the parties might invoke the asynchronous BA resource.
 
11
Standard UC constant-round protocols in the plain (fully asynchronous) UC framework do not work in this setting as, in these protocols, a party waits for all his r-round messages before proceeding to round \(r+1\), which would allow the adversary to make honest parties wait indefinitely (for messages from corrupted parties), thereby preventing them from terminating. Instead, in asynchronous protocols with eventual delivery, parties need to proceed to the next round as soon as they have sufficiently many (but not necessarily all) their messages for the current round.
 
12
We refer to [13] for a formal definition of running time in the UC framework.
 
13
Similarly to the SFE case, the adversary might prevent some of the honest parties from providing an input.
 
14
The first round starts as soon as the party receives its protocol input from the environment.
 
15
Refer to Sect. 2 for a definition of asynchronous round complexity.
 
16
Note that \(f_\textsc {prep}^\mathsf {Circ}\) actually computes a “distributed” version of the garbled circuit (described below).
 
17
Any (arithmetic or Boolean) circuit can be efficiently transformed into such a circuit.
 
18
The security required from such a cipher is roughly semantic security even if one of the keys is known (see [4] for more details). Moreover, we assume a canonical injective mapping of triples (g, x, y) to the tweak space of the cipher.
 
19
Our protocol ensures that each party eventually receives these many encrypted shares (see below).
 
20
In principle, the arithmetic circuit “re-compiler” technique by Genkin et al. [24] could also be used for this purpose, although it is not shown to work for https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-53890-6_33/435239_1_En_33_IEq210_HTML.gif nor be constant-depth. In addition, the functionality of the re-compiler is richer, as it allows to restrict possible malicious strategies during the evaluation of the circuit, which is not needed here.
 
21
USS is an adaptation of the bivariate-polynomial sharing technique [7, 33] to the asynchronous setting.
 
22
By the USS property, at this point \(p_i\) is committed to \(x_i'\) but the adversary has no information on it, i.e., the adversary holds random shares of a USS of \(x_i\).
 
23
Observe that the eventual delivery property ensures that every party will eventually receive the output.
 
24
Note that using the Berlekamp-Welch algorithm, this can be achieved efficiently.
 
25
Because [33] tolerates even \(n/3\le t<n/2\) corrupted parties, the emulation of broadcast would require an additional setup of information-theoretic pseudo-signatures [32].
 
26
The necessity of the \(t<n/3\) bound follows from the result by Canetti et al. [5, 12], who argue that this bound is necessary for fail-stop adversaries; it also applies to computational security and assuming A-BA. Moreover, note that in the asynchronous setting, all feasibility bounds are worse by an additive term of t compared to the synchronous setting. Intuitively, this stems from the fact that honest parties cannot distinguish between messages by other honest parties being delayed and messages by corrupted parties not being sent. Thus, in particular, perfectly secure asynchronous MPC is possible only if \(t < n/4\).
 
27
Nonetheless, [6] does describe an alternative way of obtaining several asynchronous BA protocols that are guaranteed to all terminate in expected constant number of rounds.
 
Literatur
1.
Simon, J.: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. ACM, Chicago (1988)
2.
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: STOC, pp. 503–513. ACM (1990)
3.
Beerliová-Trubíniová, Z., Hirt, M.: Simple and efficient perfectly-secure asynchronous MPC. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 376–392. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-76900-2_​23 CrossRef
4.
5.
Ben-Or, M., Canetti, R., Goldreich, O.: Asynchronous secure computation. In: STOC, pp. 52–61 (1993)
6.
7.
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC [1], pp. 1–10
8.
Ben-Or, M., Kelmer, B., Rabin, T.: Asynchronous secure computations with optimal resilience (extended abstract). In: PODC, pp. 183–192 (1994)
9.
10.
Bracha, G.: An asynchronou [(n-1)/3]-resilient consensus protocol. In: Probert, R.L., Lynch, N.A., Santoro, N. (eds.) 3rd ACM PODC. pp. 154–162. ACM Press, Vancouver, British Columbia, Canada (Aug 27–29, 1984)
11.
Cachin, C., Kursawe, K., Shoup, V.: Random oracles in Constantinople: Practical asynchronous byzantine agreement using cryptography. J. Cryptology 18(3), 219–246 (2005)MathSciNetCrossRefMATH
12.
13.
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press, Las Vegas, Nevada, USA (Oct 14–17, 2001)
14.
Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: 28th ACM STOC. pp. 639–648. ACM Press, Philadephia, Pennsylvania, USA (May 22–24, 1996)
15.
Canetti, R., Rabin, T.: Fast asynchronous byzantine agreement with optimal resilience. In: 25th ACM STOC, pp. 42–51. ACM Press, San Diego, California, USA (May 16–18, 1993)
16.
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: STOC [1], pp. 11–19
17.
Cohen, R.: Asynchronous secure multiparty computation in constant time. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9615, pp. 183–207. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49387-8_​8 CrossRef
18.
19.
Damgård, I., Ishai, Y.: Constant-round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378–394. Springer, Heidelberg (2005). doi:10.​1007/​11535218_​23 CrossRef
20.
21.
Feldman, P., Micali, S.: Optimal algorithms for byzantine agreement. In: 20th ACM STOC, pp. 148–161. ACM Press, Chicago, Illinois, USA (May 2–4, 1988)
22.
23.
Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. In: Fagin, R., Bernstein, P.A. (eds.) Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21–23, 1983, Colony Square Hotel, Atlanta, Georgia, USA. pp. 1–7. ACM (1983). http://​doi.​acm.​org/​10.​1145/​588058.​588060
24.
Genkin, D., Ishai, Y., Prabhakaran, M., Sahai, A., Tromer, E.: Circuits resilient to additive attacks with applications to secure computation. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. pp. 495–504 (2014). http://​doi.​acm.​org/​10.​1145/​2591796.​2591861
25.
Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)CrossRefMATH
26.
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. ACM (1987)
27.
Hirt, M., Nielsen, J.B., Przydatek, B.: Cryptographic asynchronous multi-party computation with optimal resilience. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 322–340. Springer, Heidelberg (2005). doi:10.​1007/​11426639_​19 CrossRef
28.
Hirt, M., Nielsen, J.B., Przydatek, B.: Asynchronous multi-party computation with quadratic communication. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 473–485. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-70583-3_​39 CrossRef
29.
30.
Katz, J., Koo, C.-Y.: On expected constant-round protocols for byzantine agreement. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 445–462. Springer, Heidelberg (2006). doi:10.​1007/​11818175_​27 CrossRef
31.
32.
Pfitzmann, B., Waidner, M.: Unconditional Byzantine agreement for any number of faulty processors. In: Finkel, A., Jantzen, M. (eds.) STACS 1992. LNCS, vol. 577, pp. 337–350. Springer, Heidelberg (1992). doi:10.​1007/​3-540-55210-3_​195 CrossRef
33.
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: 21st ACM STOC. pp. 73–85. ACM Press, Seattle, Washington, USA (May 15–17, 1989)
34.
Schneider, T., Zohner, M.: GMW vs. yao? efficient secure two-party computation with low depth circuits. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 275–292. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-39884-1_​23 CrossRef
35.
36.
Yao, A.C.C.: Protocols for secure computations (extended abstract). In: FOCS, pp. 160–164. IEEE (1982)
37.
Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162–167. IEEE (1986)
Metadaten
Titel
Constant-Round Asynchronous Multi-Party Computation Based on One-Way Functions
verfasst von
Sandro Coretti
Juan Garay
Martin Hirt
Vassilis Zikas
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – ASIACRYPT 2016

Print ISBN: 978-3-662-53889-0

Electronic ISBN: 978-3-662-53890-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53890-6_33