On fairness in simulatability-based cryptographic systems

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.

REFERENCES

• 1: Chagit Attiya , Danny Dolev , Joseph Gil, Asynchronous Byzantine consensus, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.119-133, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806740]
• 2: M. Backes. Unifying simulatability definitions in cryptographic systems under different timing assumptions. In R. Amadio and D. Lugiez, editors, Concurrency Theory, Proceedings of CONCUR 2003, volume 2761 of Lecture Notes in Computer Science, pages 350--365. Springer-Verlag, 2003. Full version online available at http://eprint.iacr.org/2003/114.ps.
• 3: M. Backes, D. Hofheinz, J. Müller-Quade, and D. Unruh. On fairness in simulatability-based cryptographic systems, Aug. 2005. IACR ePrint 2005/294.
• 4: Michael Backes , Birgit Pfitzmann , Michael Steiner , Michael Waidner, Polynomial Fairness and Liveness, Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW'02), p.160, June 24-26, 2002
• 5: M. Backes, B. Pfitzmann, and M. Waidner. Secure asynchronous reactive systems. IACR ePrint Archive, Mar. 2004. Online available at http://eprint.iacr.org/2004/082.ps.
• 6: Michael Ben-Or , Ran Canetti , Oded Goldreich, Asynchronous secure computation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.52-61, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167109]
• 7: Gabriel Bracha , Sam Toueg, Asynchronous consensus and broadcast protocols, Journal of the ACM (JACM), v.32 n.4, p.824-840, Oct. 1985 [doi>10.1145/4221.214134]
• 8: Christian Cachin , Klaus Kursawe , Anna Lysyanskaya , Reto Strobl, Asynchronous verifiable secret sharing and proactive cryptosystems, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586124]
• 9: Christian Cachin , Klaus Kursawe , Frank Petzold , Victor Shoup, Secure and Efficient Asynchronous Broadcast Protocols, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.524-541, August 19-23, 2001
• 10: R. Canetti. Security and composition of multi-party cryptographic protocols. Journal of Cryptology, 3(1):143--202, 2000. Full version online available at http://eprint.iacr.org/1998/018.ps.
• 11: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 12: Ran Canetti , Yehuda Lindell , Rafail Ostrovsky , Amit Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509980]
• 13: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 14: Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Distributed Computing, v.1 n.1, p.26-39, Jan. 1986 [doi>10.1007/BF01843568]
• 15: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588060]
• 16: J. A. Garay, P. MacKenzie, and K. Yang. Efficient and secure multi-party computation with faulty majority and complete fairness. IACR ePrint Archive, Jan. 2004. Online available at http://eprint.iacr.org/2004/009/.
• 17: Shafi Goldwasser , Yehuda Lindell, Secure Computation without Agreement, Proceedings of the 16th International Conference on Distributed Computing, p.17-32, October 28-30, 2002
• 18: D. Hofheinz and J. Müller-Quade. A synchronous model for multi-party computation and the incompleteness of oblivious transfer. IACR ePrint Archive, Jan. 2004. Online available at http://eprint.iacr.org/2004/016.ps.
• 19: Dennis Hofheinz , Jorn Muller-Quade , Dominique Unruh, Polynomial Runtime in Simulatability Definitions, Proceedings of the 18th IEEE Computer Security Foundations Workshop (CSFW'05), p.156-169, June 20-22, 2005 [doi>10.1109/CSFW.2005.22]
• 20: B. Pfitzmann, M. Schunter, and M. Waidner. Secure reactive systems. Technical Report RZ 3206, IBM Zurich Research Laboratory, 2000. Online available at http://www.semper.org/sirene/publ/PfSW1_00ReactSimulIBM.ps.gz.
• 21: Birgit Pfitzmann , Michael Waidner, A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.184, May 14-16, 2001
• 22: A. C.-C. Yao. Theory and applications of trapdoor functions. In 23th Annual Symposium on Foundations of Computer Science, Proceedings of FOCS 1982, pages 80--91. IEEE Computer Society, 1982.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Security

Keywords:
cryptographic protocols, fairness, scheduling, simulatability