ABSTRACT
Motivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty to every other party that did not receive the output. These works show how to design protocols for secure computation with penalties that guarantees that either fairness is guaranteed or that each honest party obtains a monetary penalty from the adversary. Protocols for this task are typically designed in an hybrid model where parties have access to a "claim-or-refund" transaction functionality denote FCR*.
In this work, we obtain improvements on the efficiency of these constructions by amortizing the cost over multiple executions of secure computation with penalties. More precisely, for computational security parameter λ, we design a protocol that implements l = poly}(λ) instances of secure computation with penalties where the total number of calls to FCR* is independent of l.
- M. Andrychowicz, S. Dziembowski, D. Malinowski, and L. Mazurek. Fair two-party computations via the bitcoin deposits. In Bitcoin Workshop, FC, 2014.Google ScholarCross Ref
- M. Andrychowicz, S. Dziembowski, D. Malinowski, and L. Mazurek. Secure multiparty computations on bitcoin. In IEEE Security and Privacy, 2014. Google ScholarDigital Library
- Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, and Lukasz Mazurek. How to deal with malleability of bitcoin transactions, 2013. Available from http://arxiv.org/pdf/1312.3230.pdf.Google Scholar
- A. Back and I. Bentov. Note on fair coin toss via bitcoin. http://arxiv.org/abs/1402.3698, 2013.Google Scholar
- S. Barber, X. Boyen, E. Shi, and E. Uzun. Bitter to better - how to make bitcoin a better currency. In Financial Cryptography, 2012.Google ScholarCross Ref
- I. Bentov and R. Kumaresan. How to use bitcoin to design fair protocols. In Crypto, 2014.Google ScholarCross Ref
- R. Cleve. Limits on the security of coin flips when half the processors are faulty. In STOC, 1986. Google ScholarDigital Library
- C. Decker and R. Wattenhofer. A fast and scalable payment network with bitcoin duplex micropayment channels. http://www.tik.ee.ethz.ch/file/716b955c130e6c703fac336ea17b1670/duplex-micropayment-channels.pdf.Google Scholar
- O. Goldreich. Foundations of cryptography vol.2. 2004. Google ScholarCross Ref
- Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game, or a completeness theorem for protocols with honest majority. 1987.Google Scholar
- Ethan Heilman, Foteini Baldimtsi, and Sharon Goldberg. Blindly signed contracts: Anonymous on-blockchain and off-blockchain bitcoin transactions. In Bitcoin Workshop, Financial Cryptography, 2016.Google ScholarCross Ref
- A. Kiayias, H-S. Zhou, and V. Zikas. Fair and robust multi-party computation using a global transaction ledger. In Eurocrypt, pages 705--734, 2016.Google ScholarCross Ref
- A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou. Hawk: The blockchain model of cryptography and privacy-preserving smart contracts. In IEEE S&P, 2016.Google Scholar
- R. Kumaresan and I. Bentov. How to use bitcoin to incentivize correct computations. In CCS, 2014. Google ScholarDigital Library
- R. Kumaresan, T. Moran, and I. Bentov. How to use bitcoin to play decentralized poker. In CCS, 2015. Google ScholarDigital Library
- R. Kumaresan, V. Vaikuntanathan, and P. Vasudevan. Improvements to secure computation with penalties. In CCS, 2016. Google ScholarDigital Library
- Alptekin Küpçü and Anna Lysyanskaya. Usable optimistic fair exchange. In CT-RSA, 2010.Google Scholar
- Andrew Y. Lindell. Legally-enforceable fairness in secure two-party computation. In CT-RSA, 2008. Google ScholarDigital Library
- G. Maxwell. 2011. https://en.bitcoin.it/wiki/Zero_Knowledge_Contingent_Payment.Google Scholar
- Rafael Pass and Abhi Shelat. Micropayments for decentralized currencies. In 22nd CCS, 2015. Google ScholarDigital Library
- J. Poon and T. Dryja. The bitcoin lightning network: Scalable off-chain instant payments. https://lightning.network/lightning-network-paper.pdf.Google Scholar
- Peter Todd. OP_CLTV, 2014. https://github.com/petertodd/bips/blob/checklocktimeverify/bip-checklocktimeverify.mediawiki.Google Scholar
- Andrew Yao. How to generate and exchange secrets (extended abstract). In FOCS, pages 162--167, 1986. Google ScholarDigital Library
Index Terms
- Amortizing Secure Computation with Penalties
Recommendations
Improvements to Secure Computation with Penalties
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications SecurityMotivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty ...
Constant-round linear-broadcast secure computation with penalties
AbstractIt is known that Bitcoin enables achieving fairness in secure computation by imposing monetary penalties on adversarial parties. This functionality is called secure computation with penalties. Bentov and Kumaresan (2014) [9] introduced the claim-...
Complete fairness in secure two-party computation
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable ...
Comments