nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Fair and Robust Multi-party Computation Using a Global Transaction Ledger

verfasst von : Aggelos Kiayias, Hong-Sheng Zhou, Vassilis Zikas

Erschienen in: Advances in Cryptology – EUROCRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Classical results on secure multi-party computation (MPC) imply that fully secure computation, including fairness (either all parties get output or none) and robustness (output delivery is guaranteed), is impossible unless a majority of the parties is honest. Recently, cryptocurrencies like Bitcoin where utilized to leverage the fairness loss in MPC against a dishonest majority. The idea is that when the protocol aborts in an unfair manner (i.e., after the adversary receives output) then honest parties get compensated by the adversarially controlled parties.

Our contribution is three-fold. First, we put forth a new formal model of secure MPC with compensation and show how the introduction of suitable ledger and synchronization functionalities makes it possible to describe such protocols using standard interactive Turing machines (ITM) circumventing the need for the use of extra features that are outside the standard model as in previous works. Second, our model, is expressed in the universal composition setting with global setup and is equipped with a composition theorem that enables the design of protocols that compose safely with each other and within larger environments where other protocols with compensation take place; a composition theorem for MPC protocols with compensation was not known before. Third, we introduce the first robust MPC protocol with compensation, i.e., an MPC protocol where not only fairness is guaranteed (via compensation) but additionally the protocol is guaranteed to deliver output to the parties that get engaged and therefore the adversary, after an initial round of deposits, is not even able to mount a denial of service attack without having to suffer a monetary penalty. Importantly, our robust MPC protocol requires only a constant number of (coin-transfer and communication) rounds.

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 Indifferentiability of Confusion-Diffusion Networks

Nächstes Kapitel Two Round Multiparty Computation via Multi-key FHE

Note that this feature is currently not fully supported.

An ITM with the special features of “wallet” and “safe” was introduced in [7] to express the ability of ITM’s to store and transfer “coins.” Such coins were treated as physical quantities that were moved between players but also locked in safes in a way that parties were then prevented to use them in certain ways (in other words such safes were not local but were affected from external events).

http://www.ethereum.org.

Certain global functionalities, such as the ledger defined in the following section, might depend on time and, therefore, need to be synchronized with the clock.

The communication channels we are using are fetch-type bounded delivery channels as in [24]. In such channels, the receiver needs to issue “fetch”-requests which are answered only if a message is ready for delivery. We refer to [24] for details.

Different protocols might proceed at a different pace.

One can make any synchronous protocol have this form by introducing dummy instructions.

This is essential to ensure that updates are done in a time-consistent manner.

We note that whenever it is clear from the context we may drop the subscript \(\bar{\mathcal {G}} \) in \(\mathsf {Q}_{\bar{\mathcal {G}}}, \mathsf {Q}^{\text {Init}}_{\bar{\mathcal {G}}}, \mathsf {Q}^{\text {Dlv}}_{\bar{\mathcal {G}}}, \mathsf {Q}^{\text {Abt}}_{\bar{\mathcal {G}}}\).

A non-reactive functionality does not accept any input from honest parties after generating output.

Delayed output delivery is a standard (G)UC mechanism where the adversary is allowed to schedule the output at a time of its choosing.

In the case of bitcoin-like ledgers these will correspond to a wallet (public-key) and a corresponding secret key.

In the case of a bitcoin-ledger this corresponds to the environment not transferring to some protocol-related wallet sufficient funds to execute the protocol.

As we will see, in bitcoin-like instantiations, \(\mathsf {Q}^{\text {Dlv}}\) will be satisfied when no honest party has a negative balance, and \(\mathsf {Q}^{\text {Abt}}\) will be satisfied when every honest party has a (strictly) positive balance.

In GUC framework [11], this is also called, \(\bar{\mathcal {G}} \)-subroutine respecting.

That is, we want to ensure that if the functionality \(\mathcal {F}_{\textsc {}} \) has guaranteed termination then the wrapped functionality will also have guaranteed termination.

Of course, the simulator needs to be given sufficiently many activation so that he can provide its own inputs and perform the simulation (please see [24] for details).

Transactions in \(\mathsf {trans} \) can also be marked with metadata.

In our construction \(\mathsf {Q}^{\text {C-Init}}_{\bar{\mathcal {G}}}\) will check additional properties for the initial set of transactions that concern \(RS^\mathtt{pub} _{P,\mathsf {sid}}\); specifically, not only that a fixed amount \(\mu \) is present but also that it is distributed in a special way.

These are commitments that can be opened so that every party agrees on whether or not the opening succeeded.

As an example, the challenge for the zero-knowledge proofs is generated by the parties opening appropriate parts of their committed random strings.

This string will be included to the Ledger’s state as soon as the transaction is posted and can be, therefore, referred to by other spending statements.

This is the case with standard Bitcoin transactions.

Looking ahead \(\mathtt{arg{2}} \) will be used to point to specific transactions of a protocol instance. The mechanism may be simulated by generating multiple addresses however it is more convenient for the protocol description and for this reason we adopt it.

That is we assume that at least one ledger rounds plus one extra clock-ticks have passed from the beginning of the time.

In an actual application, the parties will use an unfair protocol for computing the correlated randomness. As this protocol has no inputs, an abort will not be unfair (i.e., the simulator can always simulate the view of the adversary in an aborting execution.).

Recall that we assume \(|\mathcal {P} |=n\).

Note that this is a fair abort, i.e., no party has spent time into making transactions.

Throughout the following description, we say that the ledger does some check to refer to the process of checking a corresponding relation, as part of validating a special transaction.

Recall that, by definition of the clock, every party has as much time as it needs to complete all the steps below before the clock advances time.

Recall that \(R^\mathtt{pub} \) includes commitments to all parties’ private randomness (including the judge’s \(P _{d}\)) used for running the protocol, which is an implicit representation of the player set.

Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Fair two-party computations via the bitcoin deposits. In: 1st Workshop on Bitcoin Research 2014. Assocation with Financial Crypto (2014). http://eprint.iacr.org/2013/837

Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 443–458. IEEE Computer Society Press, May 2014

Asharov, G., Lindell, Y., Zarosim, H.: Fair and efficient secure multiparty computation with reputation systems. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 201–220. Springer, Heidelberg (2013)CrossRef

Asokan, N., Schunter, M., Waidner, M.: Optimistic protocols for fair exchange. In: ACM CCS 1997, pp. 7–17. ACM Press, April 1997

Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 591–606. Springer, Heidelberg (1998)CrossRef

Barak, B., Canetti, R., Lindell, Y., Pass, R., Rabin, T.: Secure computation without authentication. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 361–377. Springer, Heidelberg (2005)CrossRef

Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 421–439. Springer, Heidelberg (2014)CrossRef

Boneh, D., Naor, M.: Timed commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (2000)CrossRef

Cachin, C., Camenisch, J.L.: Optimistic fair secure computation. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 93–111. Springer, Heidelberg (2000)CrossRef

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., Walfish, S.: Universally composable security with global setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (2007)CrossRef

12.

Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001)CrossRef

13.

Canetti, R., Jain, A., Scafuro, A.: Practical UC security with a global random oracle. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 2014, pp. 597–608. ACM Press, November 2014

14.

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

15.

Canetti, R., Rabin, T.: Universal composition with joint state. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 265–281. Springer, Heidelberg (2003)CrossRef

16.

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

17.

Garay, J.A., Gelles, R., Johnson, D.S., Kiayias, A., Yung, M.: A little honesty goes a long way. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part I. LNCS, vol. 9014, pp. 134–158. Springer, Heidelberg (2015)

18.

Garay, J.A., Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Rational protocol design: cryptography against incentive-driven adversaries. In: 54th FOCS, pp. 648–657. IEEE Computer Society Press, October 2013

19.

Garay, J.A., MacKenzie, P.D., Prabhakaran, M., Yang, K.: Resource fairness and composability of cryptographic protocols. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 404–428. Springer, Heidelberg (2006)CrossRef

20.

Goldreich, O.: Foundations of Cryptography: Basic Tools, vol. 1. Cambridge University Press, Cambridge (2001)CrossRefMATH

21.

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

22.

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)CrossRef

23.

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)CrossRef

24.

Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Universally composable synchronous computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 477–498. Springer, Heidelberg (2013)CrossRef

25.

Kiayias, A., Zhou, H.-S., Zikas, V.: Fair and robust multi-party computation using a global transaction ledger. Cryptology ePrint Archive, Report 2015/574 (2015). http://eprint.iacr.org/2015/574

26.

Kosba, A., Miller, A., Shi, E., Wen, Z., Papamanthou, C.: Hawk: The blockchain model of cryptography and privacy-preserving smart contracts. Cryptology ePrint Archive, Report 2015/675, (2015). http://eprint.iacr.org/2015/675

27.

Kumaresan, R., Bentov, I.: How to use bitcoin to incentivize correct computations. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 2014, pp. 30–41. ACM Press, November 2014

28.

Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008). http://bitcoin.org/bitcoin.pdf

29.

Pinkas, B.: Fair secure two-party computation. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 87–105. Springer, Heidelberg (2003)CrossRef

30.

Ruffing, T., Kate, A., Schröder, D.: Liar, liar, coins on fire!: penalizing equivocation by loss of bitcoins. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, pp. 219–230. ACM Press, October 2015

31.

Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: 23rd FOCS, pp. 160–164. IEEE Computer Society Press, November 1982

Titel: Fair and Robust Multi-party Computation Using a Global Transaction Ledger
verfasst von: Aggelos Kiayias
Hong-Sheng Zhou
Vassilis Zikas
Verlag: Springer Berlin Heidelberg
Buch: Advances in Cryptology – EUROCRYPT 2016
Print ISBN: 978-3-662-49895-8

Electronic ISBN: 978-3-662-49896-5

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-49896-5_25

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"