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.
Category / Keywords: foundations / fairness, simulatability, cryptographic protocols, scheduling Publication Info: 3rd ACM Workshop on Formal Methods in Security Engineering, 2005 Date: received 28 Aug 2005, last revised 19 Oct 2007 Contact author: unruh at cs uni-sb de Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: Added: A section on the definition of non-trivial protocols. Version: 20071019:165824 (All versions of this report) Discussion forum: Show discussion | Start new discussion