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.
- C. Attiya, D. Dolev, and J. Gil. Asynchronous byzantine consensus. In Third Annual ACM Symposium on Principles of Distributed Computing, Proceedings of PODC 1984, pages 119--133. ACM Press, 1984.]] Google ScholarDigital Library
- 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.]]Google Scholar
- M. Backes, D. Hofheinz, J. Müller-Quade, and D. Unruh. On fairness in simulatability-based cryptographic systems, Aug. 2005. IACR ePrint 2005/294.]]Google Scholar
- M. Backes, B. Pfitzmann, M. Steiner, and M. Waidner. Polynomial fairness and liveness. In 15th IEEE Computer Security Foundations Workshop, Proceedings of CSFW 2002, pages 160--174. IEEE Computer Society, 2002. Online available at http://www.zurich.ibm.com/~mbc/papers/BPSW_02Liveness.ps.]] Google ScholarDigital Library
- 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.]]Google Scholar
- M. Ben-Or, R. Canetti, and O. Goldreich. Asynchronous secure computation. In Twenty-Fifth Annual ACM Symposium on Theory of Computing, Proceedings of STOC 1993, pages 52--61. ACM Press, 1993.]] Google ScholarDigital Library
- G. Bracha and S. Toueg. Asynchronous consensus and broadcast protocols. Journal of the ACM, 32(4):824--840, 1985.]] Google ScholarDigital Library
- C. Cachin, K. Kursawe, A. Lysyanskaya, and R. Strobl. Asynchronous verifiable secret sharing and proactive cryptosystems. In 9th ACM Conference on Computer and Communications Security, Proceedings of CCS 2002, pages 88--97. ACM Press, 2002.]] Google ScholarDigital Library
- C. Cachin, K. Kursawe, F. Petzold, and V. Shoup. Secure and efficient asynchronous broadcast protocols. In J. Kilian, editor, Advances in Cryptology, Proceedings of CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 524--541. Springer-Verlag, 2001.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42th Annual Symposium on Foundations of Computer Science, Proceedings of FOCS 2001, pages 136--145. IEEE Computer Society, 2001. Full version online available at http://www.eccc.uni-trier.de/eccc-reports/2001/TR01-016/revisn01.ps.]] Google ScholarDigital Library
- R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai. Universally composable two-party and multi-party secure computation. In 34th Annual ACM Symposium on Theory of Computing, Proceedings of STOC 2002, pages 494--503. ACM Press, 2002. Extended abstract, full version online available at http://eprint.iacr.org/2002/140.ps.]] Google ScholarDigital Library
- C. Dwork, N. A. Lynch, and L. J. Stockmayer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288--323, 1988.]] Google ScholarDigital Library
- M. J. Fischer, N. A. Lynch, and M. Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1(1):26--39, 1986.]] Google ScholarDigital Library
- M. J. Fischer, N. A. Lynch, and M. Paterson. Impossibility of distributed consensus with one faulty process. In Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Proceedings of PODS 1983, pages 1--7. ACM Press, 1983.]] Google ScholarDigital Library
- 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/.]]Google Scholar
- S. Goldwasser and Y. Lindell. Secure computation without agreement. In D. Malkhi, editor, Distributed Computing, 16th International Conference, DISC 2002, Toulouse, France, October 28-30, 2002 Proceedings, volume 2508 of Lecture Notes in Computer Science, pages 17--32. Springer, 2002.]] Google ScholarDigital Library
- 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.]]Google Scholar
- D. Hofheinz, J. Müller-Quade, and D. Unruh. Polynomial runtime in simulatability definitions. In 18th IEEE Computer Security Foundations Workshop, Proceedings of CSFW 2005, pages 156--169. IEEE Computer Society, 2005. Online available at http://iaks-www.ira.uka.de/home/unruh/publications/hofheinz05polynomial.html.]] Google ScholarDigital Library
- 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.]]Google Scholar
- B. Pfitzmann and M. Waidner. A model for asynchronous reactive systems and its application to secure message transmission. In IEEE Symposium on Security and Privacy, Proceedings of SSP 2001, pages 184--200. IEEE Computer Society, 2001. Full version online available at http://eprint.iacr.org/2000/066.ps.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
Index Terms
- On fairness in simulatability-based cryptographic systems
Recommendations
Resource Fairness and Composability of Cryptographic Protocols
We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to ...
Complete fairness in secure two-party computation
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable ...
Probabilistic Termination and Composability of Cryptographic Protocols
When analyzing the round complexity of multi-party protocols, one often overlooks the fact that underlying resources, such as a broadcast channel, can by themselves be expensive to implement. For example, it is well known that it is impossible to ...
Comments