Abstract
The fair exchange problem is key to trading electronic items in systems of mutually untrusted parties. In modern variants of such systems, each party is equipped with a security module. The security modules trust each other but can only communicate by exchanging messages through their untrusted host parties, that could drop those messages.
We describe a synchronous algorithm that ensures deterministic fair exchange if a majority of parties are honest, which is optimal in terms of resilience. If there is no honest majority, our algorithm degrades gracefully: it ensures that the probability of unfairness can be made arbitrarily low.
Our algorithm uses, as an underlying building block, an early-stopping subprotocol that solves, in a general omission failure model, a specific variant of consensus we call biased consensus. Interestingly, this modular approach combines concepts from both cryptography and distributed computing, to derive new results on the classical fair exchange problem.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asokan, N., Schunter, M., Waidner, M.: Optimistic protocols for fair exchange. In: Matsumoto, T. (ed.) 4th ACM Conference on Computer and Communications Security, Zurich, Switzerland, pp. 8–17. ACM Press, New York (1997)
Avoine, G., Gärtner, F., Guerraoui, R., Vukolić, M.: Gracefully degrading fair exchange with security modules. Technical Report IC/2004/26, EPFL, Switzerland (2004)
Avoine, G., Vaudenay, S.: Fair exchange with guardian angels. In: Chae, K.-J., Yung, M. (eds.) WISA 2003. LNCS, vol. 2908, pp. 188–202. Springer, Heidelberg (2004)
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., Pfitzmann, B., Steiner, M., Waidner, M.: Polynomial fairness and liveness. In: 15th IEEE Computer Security Foundations Workshop – CSFW, Cape Breton, Nova Scotia, Canada, pp. 160–174. IEEE, IEEE Computer Society, Los Alamitos (2002)
Bao, F., Deng, R., Mao, W.: Efficient and practical fair exchange protocols with off-line TTP. In: Proceedings of the IEEE Symposium on Research in Security and Privacy, Oakland, California, USA, pp. 77–85. IEEE Computer Society Press, Los Alamitos (1998)
Bao, F., Deng, R., Nguyen, K.Q., Varadharajan, V.: Multi-party fair exchange with an off-line trusted neutral party. In: Proceedings of the 10th International Workshop on Database & Expert Systems Applications, Florence, Italy, pp. 858–862. IEEE Computer Society Press, Los Alamitos (1999)
Baum-Waidner, B., Waidner, M.: Round-optimal and abuse-free multi-party contract signing. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 524–535. Springer, Heidelberg (2000)
Bernstein, P., Hadzilacos, V., Goodman, N.: Concurrency Control and Recovery in Database Systems. Addison-Wesley, Reading (1987)
Boneh, D., Naor, M.: Timed commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (2000)
Boyd, C., Foo, E.: Off-line fair payment protocols using convertible signatures. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 271–285. Springer, Heidelberg (1998)
Boyd, C., Kearney, P.: Exploring fair exchange protocols using specification animation. In: Okamoto, E., Pieprzyk, J.P., Seberry, J. (eds.) ISW 2000. LNCS, vol. 1975, pp. 209–223. Springer, Heidelberg (2000)
Bürk, H., Pfitzmann, A.: Value exchange systems enabling security and unobservability. Computers & Security 9(8), 715–721 (1990)
Chen, L.: Efficient fair exchange with verifiable confirmation of signatures. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 286–299. Springer, Heidelberg (1998)
Dyer, J.G., Lindemann, M., Perez, R., Sailer, R., van Doorn, L., Smith, S.W., Weingart, S.: Building the IBM 4758 secure coprocessor. IEEE Computer 34(10), 57–66 (2001)
Even, S., Yacobi, Y.: Relations amoung public key signature systems. Technical Report 175, Computer Science Department, Technicon, Haifa, Israel (1980)
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. Journal of the ACM 32(2), 374–382 (1985)
Fitzi, M., Gisin, N., Maurer, U.M., von Rotz, O.: Unconditional Byzantine agreement and multi-party computation secure against dishonest minorities from scratch. In: Proceedings of the 21st annual symposium on the Theory and Applications of Cryptographic Techniques, pp. 482–501. Springer, Heidelberg (2002)
Fitzi, M., Gottesman, D., Hirt, M., Holenstein, T., Smith, A.: Detectable Byzantine agreement secure against faulty majorities. In: Proceedings of the twenty-first annual symposium on Principles of distributed computing, pp. 118–126. ACM Press, New York (2002)
Franklin, M.K., Tsudik, G.: Secure group barter: Multi-party fair exchange with semi-trusted neutral parties. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 90–102. Springer, Heidelberg (1998)
Garay, J.A., MacKenzie, P.: Abuse-free multi-party contract signing. In: Jayanti, P. (ed.) DISC 1999. LNCS, vol. 1693, pp. 151–166. Springer, Heidelberg (1999)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game — a completeness theorem for protocols with honest majority. In: Proceedings of the 19th ACM Symposium on the Theory of Computing (STOC), pp. 218–229 (1987)
Goldwasser, S., Lindell, Y.: Secure computation without agreement. In: Proceedings of the 16th International Conference on Distributed Computing, pp. 17–32. Springer, Heidelberg (2002)
Lynch, N.: Distributed Algorithms. Morgan Kaufmann, San Mateo (1996)
Markowitch, O., Roggeman, Y.: Probabilistic non-repudiation without trusted third party. In: Proceedings of the 2nd Workshop on Security in Communication Networks (1999)
McLean, J.: A general theory of composition for a class of “possibilistic” properties. IEEE Transactions on Software Engineering 22(1), 53–67 (1996); Special Section—Best Papers of the IEEE Symposium on Security and Privacy (1994)
Pagnia, H., Vogt, H., Gärtner, F.C.: Fair exchange. The Computer Journal 46(1) (2003)
Parvédy, P.R., Raynal, M.: Optimal early stopping uniform consensus in synchronous systems with process omission failures. In: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, pp. 302–310. ACM Press, New York (2004)
Perry, K.J., Toueg, S.: Distributed agreement in the presence of processor and communication faults. IEEE Transactions on Software Engineering 12(3), 477–482 (1986)
Skeen, D.: Non-blocking commit protocols. In: Proc. ACM SIGMOD Conf., Ann Arbor, MI, p. 133 (April-May1981)
Tedrick, T.: Fair exchange of secrets. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 434–438. Springer, Heidelberg (1985)
Trusted Computing Group. Trusted computing group homepage. Internet (2003), https://www.trustedcomputinggroup.org/
Varghese, G., Lynch, N.A.: A tradeoff between safety and liveness for randomized coordinated attack. Information and Computation 128(1), 57–71 (1996)
Vogt, H., Gärtner, F.C., Pagnia, H.: Supporting fair exchange in mobile environments. ACM/Kluwer Journal on Mobile Networks and Applications (MONET) 8(2) (April 2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Avoine, G., Gärtner, F., Guerraoui, R., Vukolić, M. (2005). Gracefully Degrading Fair Exchange with Security Modules. In: Dal Cin, M., Kaâniche, M., Pataricza, A. (eds) Dependable Computing - EDCC 5. EDCC 2005. Lecture Notes in Computer Science, vol 3463. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11408901_5
Download citation
DOI: https://doi.org/10.1007/11408901_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25723-3
Online ISBN: 978-3-540-32019-7
eBook Packages: Computer ScienceComputer Science (R0)