Abstract
Fairly exchanging digital content is an everyday problem. It has been shown that fair exchange cannot be done without a trusted third party (called the Arbiter). Yet, even with a trusted party, it is still non-trivial to come up with an efficient solution, especially one that can be used in a p2p file sharing system with a high volume of data exchanged.
We provide an efficient optimistic fair exchange mechanism for bartering digital files, where receiving a payment in return to a file (buying) is also considered fair. The exchange is optimistic, removing the need for the Arbiter’s involvement unless a dispute occurs. While the previous solutions employ costly cryptographic primitives for every file or block exchanged, our protocol employs them only once per peer, therefore achieving O(n) efficiency improvement when n blocks are exchanged between two peers. The rest of our protocol uses very efficient cryptography, making it perfectly suitable for a p2p file sharing system where tens of peers exchange thousands of blocks and they do not know beforehand which ones they will end up exchanging. Therefore, our system yields to one-two orders of magnitude improvement in terms of both computation and communication (80 seconds vs. 84 minutes, 1.6MB vs. 100MB). Thus, for the first time, a provably secure (and privacy respecting when payments are made using e-cash) fair exchange protocol is being used in real bartering applications (e.g., BitTorrent) [14] without sacrificing performance.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Asokan, N., Janson, P.A., Steiner, M., Waidner, M.: The state of the art in electronic payment systems. IEEE Computer 30, 28–35 (1997)
Asokan, N., Schunter, M., Waidner, M.: Optimistic Protocols for Fair Exchange. In: CCS (1997)
Asokan, N., Shoup, V., Waidner, M.: Asynchronous protocols for optimistic fair exchange. In: IEEE Security and Privacy (1998)
Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures. IEEE Journal on Selected Areas in Communications 18(4), 591–610 (2000)
Ateniese, G.: Efficient verifiable encryption (and fair exchange) of digital signatures. In: CCS (1999)
Avoine, G., Vaudenay, S.: Optimistic Fair Exchange Based on Publicly Verifiable Secret Sharing. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 74–85. Springer, Heidelberg (2004)
Backes, M., Datta, A., Derek, A., Mitchell, J.C., Turuani, M.: Compositional analysis of contract-signing protocols. Theoretical Computer Science 367(1-2), 33–56 (2006)
Belenkiy, M., Chase, M., Erway, C.C., Jannotti, J., Küpçü, A., Lysyanskaya, A., Rachlin, E.: Making P2P Accountable without Losing Privacy. In: WPES (2007)
Belenkiy, M., Chase, M., Erway, C.C., Jannotti, J., Küpçü, A., Lysyanskaya, A.: Incentivizing Outsourced Computation. In: NetEcon (2008)
Bellare, M., Rogaway, P.: Optimal Asymmetric Encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995)
Ben-Or, M., Goldreich, O., Micali, S., Rivest, R.L.: A fair protocol for signing contracts. IEEE Transactions on Information Theory 36(1), 40–46 (1990)
Blakley, G.R.: Safeguarding cryptographic keys. In: National Computer Conference (1979)
Boneh, D., Naor, M.: Timed commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, p. 236. Springer, Heidelberg (2000)
Brownie Project, http://cs.brown.edu/research/brownie
Camenisch, J., Damgård, I.: Verifiable Encryption, Group Encryption, and Their Applications to Group Signatures and Signature Sharing Schemes. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, p. 331. Springer, Heidelberg (2000)
Camenisch, J., Hohenberger, S., Kohlweiss, M., Lysyanskaya, A., Meyerovich, M.: How to Win the Clonewars: Efficient Periodic N-times Anonymous Authentication. In: CCS (2006)
Camenisch, J.L., Hohenberger, S., Lysyanskaya, A.: Compact e-cash. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 302–321. Springer, Heidelberg (2005)
Camenisch, J., Lysyanskaya, A., Meyerovich, M.: Endorsed e-cash. IEEE Security and Privacy (2007)
Camenisch, J., Shoup, V.: Practical verifiable encryption and decryption of discrete logarithms. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 126–144. Springer, Heidelberg (2003)
Chaum, D.: Bling signatures for untraceable payments. In: CRYPTO (1982)
Chaum, D., den Boer, B., van Heyst, E., Mjolsnes, S., Steenbeek, A.: Efficient offline electronic checks. In: EUROCRYPT (1990)
Cohen, B.: Incentives build robustness in bittorrent. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol. 2735, Springer, Heidelberg (2003)
Cohen, L.: Testimony of Larry Cohen, President of Communications Workers of America (May 2007)
Cramer, R., Shoup, V.: A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 13. Springer, Heidelberg (1998)
Daemen, J., Rijmen, V.: The Design of Rijndael: AES–the Advanced Encryption Standard. Springer books (2002)
Dingledine, R., Mathewson, N., Syverson, P.: Tor: The second-generation onion router. In: USENIX Security (2004)
Dodis, Y., Lee, P.J., Yum, D.H.: Optimistic Fair Exchange in a Multi-user Setting. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 118–133. Springer, Heidelberg (2007)
Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM Journal on Computing (2000)
Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSA-OAEP Is Secure under the RSA Assumption. Journal of Cryptology 17(2), 81–104 (2004)
Garay, J., Jakobsson, M., MacKenzie, P.: Abuse-free optimistic contract signing. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 449. Springer, Heidelberg (1999)
Goldwasser, S., Micali, S., Rivest, R.: A Digital Signature Scheme Secure Against Adaptive Chosen Message Attack. SIAM Journal on Computing (1988)
Iosup, A., Garbacki, P., Pouwelse, J., Epema, D.H.J.: Correlating Topology and Path Characteristics of Overlay Networks and the Internet. In: GP2PC (2006)
Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman and Hall/CRC Press, Boca Raton (2007)
Küpçü, A., Lysyanskaya, A.: Optimistic Fair Exchange with Multiple Arbiters. Cryptology ePrint Archive, Report 2009/069 (2009), http://eprint.iacr.org/2009/069
Küpçü, A., Lysyanskaya, A.: Usable Optimistic Fair Exchange. Cryptology ePrint Archive, Report 2008/431 (2008), http://eprint.iacr.org/2008/431
Lindell, Y.: Legally Enforceable Fairness in Secure Two-Party Computation. In: Malkin, T.G. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 121–137. Springer, Heidelberg (2008)
Markowitch, O., Saeednia, S.: Optimistic fair exchange with transparent signature recovery. In: Syverson, P.F. (ed.) FC 2001. LNCS, vol. 2339, p. 329. Springer, Heidelberg (2002)
Merkle, R.: A digital signature based on a conventional encryption function. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 369–378. Springer, Heidelberg (1988)
Micali, S.: Simultaneous Electronic Transactions. U.S. Patent, No. 5,666,420 (1997)
Micali, S.: Simple and fast optimistic protocols for fair electronic exchange. In: PODC (2003)
Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: STOC (1989)
NIST. Digital Signature Standard (DSS). FIPS, PUB 186-2 (2000)
Pagnia, H., Gärtner, F.C.: On the impossibility of fair exchange without a trusted third party. Technical Report, TUD-BS-1999-02 (1999)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 223. Springer, Heidelberg (1999)
Shamir, A.: How to Share a Secret. ACM Communications (1979)
Shmatikov, V., Mitchell, J.C.: Finite-state analysis of two contract signing protocols. Theoretical Computer Science 283(2), 419–450 (2002)
Shoup, V., Gennaro, R.: Securing threshold cryptosystems against chosen ciphertext attack. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 1–16. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Küpçü, A., Lysyanskaya, A. (2010). Usable Optimistic Fair Exchange. In: Pieprzyk, J. (eds) Topics in Cryptology - CT-RSA 2010. CT-RSA 2010. Lecture Notes in Computer Science, vol 5985. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11925-5_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-11925-5_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11924-8
Online ISBN: 978-3-642-11925-5
eBook Packages: Computer ScienceComputer Science (R0)