Cryptology ePrint Archive: Report 2005/294

On Fairness in Simulatability-based Cryptographic Systems

Michael Backes and Dennis Hofheinz and Jörn Müller-Quade and Dominique Unruh

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.

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 format(s): 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)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]