International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On Fairness in Simulatability-based Cryptographic Systems

Michael Backes
Dennis Hofheinz
Jörn Müller-Quade
Dominique Unruh
Search ePrint
Search Google
Abstract: Simulatability constitutes the cryptographic notion of a secure refinement and has asserted its position as one of the fundamental concepts of modern cryptography. Although simulatability carefully captures that a distributed protocol does not behave any worse than an ideal specification, it however does not capture any form of liveness guarantees, i.e., that something good eventually happens in the protocol. We show how one can extend the notion of simulatability to comprise liveness guarantees by imposing specific fairness constraints on the adversary. As the common notion of fairness based on infinite runs and eventual message delivery is not suited for reasoning about polynomial-time, cryptographic systems, we propose a new definition of fairness that enforces the delivery of messages after a polynomial number of steps. We provide strengthened variants of this definition by granting the protocol parties explicit guarantees on the maximum delay of messages. The variants thus capture fairness with explicit timeout signals, and we further distinguish between fairness with local timeouts and fairness with global timeouts. We compare the resulting notions of fair simulatability, and provide separating examples that help to classify the strengths of the definitions and that show that the different definitions of fairness imply different variants of simulatability.
  title={On Fairness in Simulatability-based Cryptographic Systems},
  booktitle={IACR Eprint archive},
  keywords={foundations / fairness, simulatability, cryptographic protocols, scheduling},
  note={3rd ACM Workshop on Formal Methods in Security Engineering, 2005 13805 received 28 Aug 2005, last revised 19 Oct 2007},
  author={Michael Backes and Dennis Hofheinz and Jörn Müller-Quade and Dominique Unruh},