Cited By
View all- Orzan STorabi Dashti M(2008)Fair Exchange Is Incomparable to ConsensusProceedings of the 5th international colloquium on Theoretical Aspects of Computing10.1007/978-3-540-85762-4_24(349-363)Online publication date: 1-Sep-2008
A Topological Condition for Solving Fair Exchange in Byzantine Environments
Pages 30 - 49
Abstract
In this paper, we study the solvability of fair exchange in the context of Byzantine failures. In doing so, we first present a generic model with trusted and untrusted processes, and propose a specification of the fair exchange problem that clearly separates safety and liveness, via fine-grained properties. We then show that the solvability of fair exchange depends on a necessary and sufficient topological condition, which we name the reachable majority condition. The first part of this result, i.e., the condition is necessary, was shown in a companion paper and is briefly recalled here. The second part, i.e., the condition is sufficient, is the focal point of this paper. The correctness proof of this second part consists in proposing a solution to fair exchange in the aforementioned model.
References
[1]
Avoine, G., Gärtner, F., Guerraoui, R., Kursawe, K., Vaudenay, S., Vukolic, M.: Reducing fair exchange to atomic commit. Technical report, Swiss Federal Institute of Technology (EPFL) (2004)
[2]
Avoine G., Gärtner F., Guerraoui R., and Vukolic M. Dal Cin M., Kaâniche M., and Pataricza A. Gracefully degrading fair exchange with security modules (extended abstract) Dependable Computing - EDCC 2005 2005 Heidelberg Springer 55-71
[3]
Avoine, G., Vaudenay, S.: Fair exchange with guardian angels. Technical report, Swiss Federal Institute of Technology (EPFL) (2003)
[4]
Garbinato B. and Rickebusch I. Impossibility results on fair exchange Proceedings of the 6th International Workshop on Innovative Internet Community Systems (I2CS 2006) 2006 Heidelberg Springer
[5]
Asokan N., Shoup V., and Waidner M. Optimistic fair exchange of digital signatures IEEE Journal on Selected Area in Communications 2000 18 593-610
[6]
Dyer J., Lindemann M., Perez R., Sailer R., van Doorn L., Smith S., and Weingart S. Building the IBM 4758 secure coprocessor Computer 2001 34 10 57-66
[7]
Bajikar, S.: Trusted Platform Module (TPM) based Security on Notebook PCs – White Paper. Intel Corporation – Mobile Platforms Group. (2002)
[8]
Doudou A., Garbinato B., and Guerraoui R. Tolerating Arbitrary Failures with State Machine Replication Dependable Computing Systems: Paradigms, Performance Issues, and Applications 2005 Chichester Wiley 27-56
[9]
Chandra T.D. and Toueg S. Unreliable failure detectors for reliable distributed systems Journal of the ACM 1996 43 2 225-267
[10]
Hadzilacos, V., Toueg, S.: Fault-tolerant broadcasts and related problems, pp. 97–145 (1993)
[11]
Pagnia, H., Gärtner, F.: On the impossibility of fair exchange without a trusted third party. Technical report, Swiss Federal Institute of Technology (EPFL) (1999)
[12]
Drabkin V., Friedman R., and Segal M. Efficient byzantine broadcast in wireless ad-hoc networks DSN 2005: Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN 2005) 2005 Los Alamitos IEEE Computer Society 160-169
[13]
Lamport L., Shostak R., and Pease M. The byzantine generals problem ACM Transactions on Programming Languages and Systems 1982 4 3 382-401
[14]
Pease M., Shostak R., and Lamport L. Reaching agreement in the presence of faults Journal of the ACM 1980 27 2 228-234
[15]
Markowitch O., Gollmann D., and Kremer S. Lee P.J. and Lim C.H. On fairness in exchange protocols Information Security and Cryptology - ICISC 2002 2003 Heidelberg Springer 451-464
[16]
Ray, I., Ray, I.: Fair exchange in e-commerce. SIGecom Exchanges 3(2) (2002)
[17]
Ateniese G. Efficient verifiable encryption (and fair exchange) of digital signatures CCS 1999: Proceedings of the 6th ACM conference on Computer and communications security 1999 New York ACM Press 138-146
[18]
Franklin M. and Reiter M. Fair exchange with a semi-trusted third party (extended abstract) CCS 1997: Proceedings of the 4th ACM conference on Computer and communications security 1997 New York ACM Press 1-5
[19]
Micali S. Simple and fast optimistic protocols for fair electronic exchange PODC 2003: Proceedings of the twenty-second annual symposium on Principles of distributed computing 2003 New York ACM Press 12-19
[20]
Ray I., Ray I., and Natarajan N. An anonymous and failure resilient fair-exchange e-commerce protocol Decision Support Systems 2005 39 3 267-292
[21]
Fischer M., Lynch N., and Paterson M. Impossibility of Distributed Consensus with One Faulty Process J. ACM 1985 32 374-382
[22]
Even, S., Yacobi, Y.: Relations among public key signature systems. Technical report, Technion - Israel Institute of Technology (1980)
[23]
Ketchpel, S., García-Molina, H.: Making trust explicit in distributed commerce transactions. In: Proceedings of the International Conference on Distributed Computing Systems (1995)
[24]
Chaum D., Crépeau C., and Damgard I. Multiparty unconditionally secure protocols STOC 1988: Proceedings of the 20th ACM symposium on Theory of computing 1988 New York ACM Press 11-19
[25]
Goldreich O. The Foundations of Cryptography 2004 Cambridge Cambridge University Press
[26]
Bürk H. and Pfitzmann A. Value exchange systems enabling security and unobservability Computers & Security 1990 9 9 715-721
[27]
Bao, F., Deng, R.H., Mao, W.: Efficient and practical fair exchange protocols with off-line TTP. In: RSP: 19th IEEE Computer Society Symposium on Research in Security and Privacy (1998)
[28]
Baum-Waidner B. and Waidner M. Welzl E., Montanari U., and Rolim J.D.P. Round-optimal and abuse free optimistic multi-party contract signing Automata, Languages and Programming 2000 Heidelberg Springer 524-535
[29]
Srivatsa M., Xiong L., and Liu L. Exchangeguard: A distributed protocol for electronic fair-exchange 19th International Parallel and Distributed Processing Symposium (IPDPS 2005) 2005 Los Alamitos IEEE Computer Society
[30]
Goldwasser S. and Levin L. Menezes A. and Vanstone S.A. Fair computation of general functions in presence of immoral majority Advances in Cryptology - CRYPTO ’90 1991 Heidelberg Springer 77-93
Recommendations
Analysis on Cyclic Multi-party Fair Exchange Protocols
CSSE '08: Proceedings of the 2008 International Conference on Computer Science and Software Engineering - Volume 03A multi-party fair exchange protocol allows several parties to exchange commodities in such a way that everyone gives an item away if and only if it receives an expected item in return. In this paper, we review an important cyclic multi-party fair ...
Optimistic fair exchange with multiple arbiters
ESORICS'10: Proceedings of the 15th European conference on Research in computer securityFair exchange is one of the most fundamental problems in secure distributed computation. Alice has something that Bob wants, and Bob has something that Alice wants. A fair exchange protocol would guarantee that, even if one of them maliciously deviates ...
An optimistic fair exchange protocol and its security in the universal composability framework
Fair exchange protocols allow both or neither of two parties to obtain the other's items, and this property is essential in e-commerce. In this paper, we construct an optimistic fair exchange protocol that is applicable to any digital signature by ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
568 pages
© Springer-Verlag Berlin Heidelberg 2006.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 04 December 2006
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Nov 2024
Other Metrics
Citations
Cited By
View all- Orzan STorabi Dashti M(2008)Fair Exchange Is Incomparable to ConsensusProceedings of the 5th international colloquium on Theoretical Aspects of Computing10.1007/978-3-540-85762-4_24(349-363)Online publication date: 1-Sep-2008
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in