Abstract
Existing communication models for multiparty computation (MPC) either assume that all messages are delivered eventually or any message can be lost. Under the former assumption, MPC protocols guaranteeing output delivery are known. However, this assumption may not hold in some network settings like the Internet where messages can be lost due to denial of service attack or heavy network congestion. On the other hand, the latter assumption may be too conservative. Known MPC protocols developed under this assumption have an undesirable feature: output delivery is not guaranteed even only one party suffers message loss.
In this work, we propose a communication model which makes an intermediate assumption on message delivery. In our model, there is a common global clock and three types of parties: (i) Corrupted parties (ii) Honest parties with connection problems (where message delivery is never guaranteed) (iii) Honest parties that can normally communicate but may lose a small fraction of messages at each round due to transient network problems. We define secure MPC under this model. Output delivery is guaranteed to type (ii) parties that do not abort and type (iii) parties.
Let n be the total number of parties, e f and e c be upper bounds on the number of corrupted parties and type (ii) parties respectively. We construct a secure MPC protocol for n > 4e f + 3e c . Protocols for broadcast and verifiable secret sharing are constructed along the way.
Supported by NSF Trusted Computing grant #0310751.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-540-32732-5_32
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Beaver, D.: Multiparty protocols tolerating half faulty processors. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 560–572. Springer, Heidelberg (1990)
Ben-Or, M., Canetti, R., Goldreich, O.: Asynchronous secure computation. In: STOC 1993: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pp. 52–61. ACM Press, New York (1993)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: Proceedings of the 20th annual ACM symposium on Theory of computing, pp. 1–10 (1988)
Ben-Or, M., Kelmer, B., Rabin, T.: Asynchronous secure computations with optimal resilience (extended abstract). In: PODC 1994: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, pp. 183–192. ACM Press, New York (1994)
Berman, P., Garay, J.A., Perry, K.J.: Towards optimal distributed consensus (extended abstract). In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 410–415. IEEE, Los Alamitos (1989)
Biely, M.: Optimal agreement protocol in malicious faulty processors and faulty links. IEEE Transactions on Knowledge and Data Engineering 4(3), 266–280 (1992)
Canetti, R.: Studies in Secure Multiparty Computation and Applications. PhD thesis, Weizmann Institute of Science, Rehovot 76100, Israel (June 1995)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: FOCS 2001: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, Washington, DC, USA, p. 136. IEEE Computer Society, Los Alamitos (2001)
Canetti, R., Halevi, S., Herzberg, A.: Maintaining authenticated communication in the presence of break-ins. In: PODC 1997: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, pp. 15–24. ACM Press, New York (1997)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable twoparty and multi-party secure computation. In: STOC 2002: Proceedings of the thiryfourth annual ACM symposium on Theory of computing, pp. 494–503. ACM Press, New York (2002)
Chaum, D., Crepeau, C., Damgard, I.: Multiparty unconditionally secure protocols. In: STOC 1988: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 11–19. ACM Press, New York (1988)
Cramer, R., Damgård, I., Dziembowski, S., Hirt, M., Rabin, T.: Efficient multiparty computations secure against an adaptive adversary. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 311–326. Springer, Heidelberg (1999)
Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. 26(4), 873–933 (1997)
Garay, J.A., Perry, K.J.: A continuum of failure models for distributed computing. In: Proceedings of the 6th International Workshop on Distributed Algorithms, pp. 153–165. Springer, Heidelberg (1992); Full version availabe at, http://cm.belllabs.com/who/garay/continuum.ps
Gennaro, R., Rabin, M.O., Rabin, T.: Simplified vss and fast-track multiparty computations with applications to threshold cryptography. In: PODC 1998: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pp. 101–111. ACM Press, New York (1998)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the nineteenth annual ACM conference on Theory of computing, pp. 218–229. ACM Press, New York (1987)
Goldwasser, S., Lindell, Y.: Secure computation without agreement. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol. 2508, pp. 17–32. Springer, Heidelberg (2002)
Kalai, Y.T., Lindell, Y., Prabhakaran, M.: Concurrent general composition of secure protocols in the timing model. In: STOC 2005: Proceedings of the thirtyseventh annual ACM symposium on Theory of computing, pp. 644–653. ACM Press, New York (2005)
Keromytis, A.D., Misra, V., Rubenstein, D.: Sos: secure overlay services. SIGCOMM Comput. Commun. Rev. 32(4), 61–72 (2002)
Parvédy, P.R., Raynal, M.: Optimal early stopping uniform consensus in synchronous systems with process omission failures. In: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, pp. 302–310. ACM Press, New York (2004)
Perry, K.J., Toueg, S.: Distributed agreement in the presence of processor and communication faults. IEEE Trans. Softw. Eng. 12(3), 477–482 (1986)
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority. In: STOC 1989: Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 73–85. ACM Press, New York (1989)
Schmid, U., Weiss, B., Rushby, J.: Formally verified byzantine agreement in presence of link faults. In: ICDCS 2002: Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS 2002), Washington, DC, USA, p. 608. IEEE Computer Society, Los Alamitos (2002)
Thambidurai, P., Park, Y.-K.: Interactive consistency with multiple failure modes. In: Proceedings of the 7th Reliable Distributed Systems Symposium, pp. 93–100 (1988)
Yan, K.Q., Chin, Y.H., Wang, S.C.: Optimal agreement protocol in malicious faulty processors and faulty links. IEEE Transactions on Knowledge and Data Engineering 4(3), 266–280 (1992)
Yao, A.C.-C.: Protocols for secure computations. In: FOCS 1982: Proceedings of the 23rd Symposium on Foundations of Computer Science, pp. 160–164. IEEE Computer Society Press, Los Alamitos (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koo, CY. (2006). Secure Computation with Partial Message Loss. In: Halevi, S., Rabin, T. (eds) Theory of Cryptography. TCC 2006. Lecture Notes in Computer Science, vol 3876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11681878_26
Download citation
DOI: https://doi.org/10.1007/11681878_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32731-8
Online ISBN: 978-3-540-32732-5
eBook Packages: Computer ScienceComputer Science (R0)