Abstract
We study a model of fairness in secure computation in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty. We then show how the Bitcoin network can be used to achieve the above notion of fairness in the two-party as well as the multiparty setting (with a dishonest majority). In particular, we propose new ideal functionalities and protocols for fair secure computation and fair lottery in this model.
One of our main contributions is the definition of an ideal primitive, which we call \(\mathcal{F}_{\mathrm{CR}}^\star\) (CR stands for “claim-or-refund”), that formalizes and abstracts the exact properties we require from the Bitcoin network to achieve our goals. Naturally, this abstraction allows us to design fair protocols in a hybrid model in which parties have access to the \(\mathcal{F}_{\mathrm{CR}}^\star\) functionality, and is otherwise independent of the Bitcoin ecosystem. We also show an efficient realization of \(\mathcal{F}_{\mathrm{CR}}^\star\) that requires only two Bitcoin transactions to be made on the network.
Our constructions also enjoy high efficiency. In a multiparty setting, our protocols only require a constant number of calls to \(\mathcal{F}_{\mathrm{CR}}^\star\) per party on top of a standard multiparty secure computation protocol. Our fair multiparty lottery protocol improves over previous solutions which required a quadratic number of Bitcoin transactions.
Chapter PDF
Similar content being viewed by others
References
Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Fair two-party computations via the bitcoin deposits, ePrint 2013/837 (2013)
Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: IEEE Security and Privacy (2014)
Asharov, G.: Towards characterizing complete fairness in secure two-party computation. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 291–316. Springer, Heidelberg (2014)
Asokan, N., Shoup, V., Waidner, M.: Optimistic protocols for fair exchange. In: ACM CCS, pp. 7–17 (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)
Back, A., Bentov, I.: Note on fair coin toss via bitcoin (2013), http://arxiv.org/abs/1402.3698
Barber, S., Boyen, X., Shi, E., Uzun, E.: Bitter to better — how to make bitcoin a better currency. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 399–414. Springer, Heidelberg (2012)
Beaver, D., Goldwasser, S.: Multiparty computation with faulty majority. In: IEEE FOCS, pp. 468–473 (1989)
Beimel, A., Lindell, Y., Omri, E., Orlov, I.: 1/p-Secure Multiparty Computation without Honest Majority and the Best of Both Worlds. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 277–296. Springer, Heidelberg (2011)
Belenkiy, M., Chase, M., Erway, C., Jannotti, J., Kupcu, A., Lysyanskaya, A., Rachlin, E.: Making p2p accountable without losing privacy. In: Proc. of WPES (2007)
Ben-Or, M., Goldreich, O., Micali, S., Rivest, R.: A fair protocol for signing contracts (extended abstract). In: Brauer, W. (ed.) ICALP. LNCS, vol. 194, pp. 43–52. Springer, Heidelberg (1985)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: ACM STOC (1988)
Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols, ePrint 2014/129 (2014)
Boneh, D., Naor, M.: Timed Commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (2000)
Cachin, C., Camenisch, J.L.: Optimistic Fair Secure Computation. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 93–111. Springer, Heidelberg (2000)
Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: IEEE FOCS, pp. 136–145 (2001)
Canetti, R., Kushilevitz, E., Lindell, Y.: On the limitations of universally composable two-party computation without set-up assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 68–86. Springer, Heidelberg (2003)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: ACM STOC, pp. 11–19 (1988)
Chen, L., Kudla, C., Paterson, K.G.: Concurrent Signatures. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 287–305. Springer, Heidelberg (2004)
Clark, J., Essex, A.: CommitCoin: Carbon Dating Commitments with Bitcoin. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 390–398. Springer, Heidelberg (2012)
Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: STOC, pp. 364–369 (1986)
Friedman, E., Resnick, P.: The social cost of cheap pseudonyms. Journal of Economics and Management Strategy, 173–199 (2000)
Garay, J., Jakobsson, M.: Timed release of standard digital signatures. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 168–182. Springer, Heidelberg (2003)
Garay, J.A., Jakobsson, M., MacKenzie, P.D.: Abuse-Free Optimistic Contract Signing. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 449–466. Springer, Heidelberg (1999)
Garay, J., Katz, J., Kumaresan, R., Zhou, H.-S.: Adaptively secure broadcast, revisited. In: ACM PODC, pp. 179–186 (2011)
Garay, J., MacKenzie, P., Prabhakaran, M., Yang, K.: Resource fairness and composability of cryptographic protocols. In: TCC, pp. 404–428 (2006)
Garay, J.A., Pomerance, C.: Timed fair exchange of standard signatures. In: Wright, R.N. (ed.) FC 2003. LNCS, vol. 2742, pp. 190–207. Springer, Heidelberg (2003)
Goldreich, O.: Foundations of cryptography: Basic Applications, vol. 2 (2004)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game, or a completeness theorem for protocols with honest majority. In: ACM STOC, pp. 218–229 (1987)
Goldwasser, S., Levin, L.A.: Fair Computation of General Functions in Presence of Immoral Majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 77–93. Springer, Heidelberg (1991)
Gordon, S., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. In: ACM STOC, pp. 413–422 (2008)
Gordon, D., Ishai, Y., Moran, T., Ostrovsky, R., Sahai, A.: On Complete Primitives for Fairness. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 91–108. Springer, Heidelberg (2010)
Gordon, S.D., Katz, J.: Partial Fairness in Secure Two-Party Computation. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 157–176. Springer, Heidelberg (2010)
Huang, Y., Katz, J., Evans, D.: Private set intersection: Are garbled circuits better than custom protocols? In: NDSS (2012)
Huang, Y., Katz, J., Kolesnikov, V., Kumaresan, R., Malozemoff, A.J.: Amortizing Garbled Circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 458–475. Springer, Heidelberg (2014)
Ishai, Y., Prabhakaran, M., Sahai, A.: Founding Cryptography on Oblivious Transfer – Efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008)
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)
Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer – efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008)
Küpçü, A., Lysyanskaya, A.: Optimistic Fair Exchange with Multiple Arbiters. In: Gritzalis, D., Preneel, B., Theoharidou, M. (eds.) ESORICS 2010. LNCS, vol. 6345, pp. 488–507. Springer, Heidelberg (2010)
Küpçü, A., Lysyanskaya, A.: Usable Optimistic Fair Exchange. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 252–267. Springer, Heidelberg (2010)
Lindell, A.Y.: Legally-enforceable fairness in secure two-party computation. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 121–137. Springer, Heidelberg (2008)
Lindell, Y., Riva, B.: Cut-and-Choose Yao-Based Secure Computation in the Online/Offline and Batch Settings. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 476–494. Springer, Heidelberg (2014)
Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay: a secure two-party computation system. In: USENIX, p. 20 (2004)
Maxwell, G.: Zero knowledge contingent payment (2011), https://en.bitcoin.it/wiki/Zero_Knowledge_Contingent_Payment
Micali, S.: Simple and fast optimistic protocols for fair electronic exchange. In: ACM PODC, pp. 12–19 (2003)
Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008), http://bitcoin.org/bitcoin.pdf
Naor, M.: Bit Commitment Using Pseudo-randomness. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 128–136. Springer, Heidelberg (1990)
Pinkas, B.: Fair secure two-party computation. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 87–105. Springer, Heidelberg (2003)
Yao, A.C.-C.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science (FOCS), pp. 162–167. IEEE (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 International Association for Cryptologic Research
About this paper
Cite this paper
Bentov, I., Kumaresan, R. (2014). How to Use Bitcoin to Design Fair Protocols. In: Garay, J.A., Gennaro, R. (eds) Advances in Cryptology – CRYPTO 2014. CRYPTO 2014. Lecture Notes in Computer Science, vol 8617. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44381-1_24
Download citation
DOI: https://doi.org/10.1007/978-3-662-44381-1_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44380-4
Online ISBN: 978-3-662-44381-1
eBook Packages: Computer ScienceComputer Science (R0)