Abstract
This paper improves on the classical results in unconditionally secure multi-party computation among a set of n players, by considering a model with three simultaneously occurring types of player corruption: the adversary can actively corrupt (i.e. take full control over) up to t a players and, additionally, can passively corrupt (i.e. read the entire information of) up to t p players and fail-corrupt (i.e. stop the computation of) up to t f other players. The classical results in multi-party computation are for the special cases of only passive (t a=t f = 0) or only active (t p=t f = 0) corruption. In the passive case, every function can be computed securely if and only if t p < n/2. In the active case, every function can be computed securely if and only if t a < n/3; when a broadcast channel is available, then this bound is t a < n/2. These bounds are tight.
Strictly improving these results, one of our results states that, in addition to tolerating t a < n/3 actively corrupted players, privacy can be guaranteed against every minority, thus tolerating additional t p ≤ n/6 passively corrupted players. These protocols require no broadcast and have an exponentially small failure probability. When zero failure probability is required, privacy can be maintained against any minority, but one can even tolerate t a ≤ n/4 of these players to be corrupted actively. We further show that the bound t < n/2 for passive corruption holds even if the adversary is additionally allowed to make the passively corrupted players fail.
Moreover, we characterize completely the achievable thresholds t a, t p and t f for four scenarios. Zero failure probability is achievable if and only if 2t a + 2t p + t f < n and 3t a + t p + t f < n; this holds whether or not a broadcast channel is available. Exponentially small failure probability with a broadcast channel is achievable if and only if 2t a + 2t p + t f<n; without broadcast, the additional condition 3t a + t f < n is necessary and sufficient.
Research supported by the Swiss National Science Foundation (SNF), SPP project no. 5003-045293.
Chapter PDF
Key words
References
M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proc. 20th ACM Symposium on the Theory of Computing (STOC), pages 1–10, 1988.
R. Canetti. Studies in Secure Multiparty Computation and Applications. PhD thesis, Weizmann Institute of Science, Rehovot 76100, Israel, June 1995.
R. Canetti. Modular composition of multi-party cryptographic protocols, Nov. 1997. Manuscript.
R. Canetti. Security and composition of multi-party cryptographic protocols, June 1998. Manuscript.
D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols (extended abstract). In Proc. 20th ACM Symposium on the Theory of Computing (STOC), pages 11–19, 1988.
D. Chaum, I. Damgård, and J. van de Graaf. Multiparty computations ensuring privacy of each party's input and correctness of the result. In Advances in Cryptology — CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 87–119. Springer-Verlag, 1987.
R. Cramer, I. Damgård, and U. Maurer. Span programs and general multi-party computation. Manuscript, 1998.
R. Canetti, U. Feige, O. Goldreich, and M. Naor. Adaptively secure multi-party computation. In Proc. 28th ACM Symposium on the Theory of Computing (STOC), pages 639–648, Nov. 1996.
R. Cramer, M. K. Franklin, B. Schoenmakers, and M. Yung. Multi-authority secret-ballot elections with linear work. In Advances in Cryptology — EUROCRYPT '96, volume 1070 of lecture Notes in Computer Science, pages 72–83. IACR, Springer-Verlag, May 1996.
R. Canetti and R. Gennaro. Incoercible multiparty computation. In Proc. 37th IEEE Symposium on the Foundations of Computer Science (FOCS), 1996.
B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In Proc. 36th IEEE Symposium on the Foundations of Computer Science (FOCS), pages 41–51, Oct. 1995.
C. Crépeau, J. van de Graaf, and A. Tapp. Committed oblivious transfer and private multi-party computation. In Advances in Cryptology — CRYPTO '95, volume 963 of Lecture Notes in Computer Science, pages 110–123. Springer-Verlag, 1995.
D. Chaum. The spymasters double-agent problem. In Advances in Cryptology — CRYPTO '89, volume 435 of Lecture Notes in Computer Science, pages 591–602. Springer-Verlag, 1989.
D. Dolev, C. Dwork, O. Waarts, and M. Yung. Perfectly secure message transmission. Journal of the ACM, 40(1): 17–47, Jan. 1993.
C. Dwork. Strong verifiable secret sharing. In Proc. 4th International Workshop on Distributed Algorithms '90, volume 486 of Lecture Notes in Computer Science, pages 213–227. Springer-Verlag, 1990.
U. Feige, J. Kilian, and M. Naor. A minimal model for secure computation. In Proc. 26th ACM Symposium on the Theory of Computing (STOC), pages 554–563, 1994.
P. Feldman and S. Micali. Optimal algorithms for Byzantine agreement. In Proc. 20th ACM Symposium on the Theory of Computing (STOC), pages 148–161, 1988.
M. K. Franklin and M. K. Reiter. The design and implementation of a secure auction service. IEEE Transactions on Software Engineering, 22(5):302–312, May 1996.
M. K. Franklin. Complexity and Security of Distributed Protocols. PhD thesis, Columbia University, 1993.
M. K. Franklin and M. Yung. Communication complexity of secure computation. In Proc. 24th ACM Symposium on the Theory of Computing (STOC), pages 699–710, 1992.
Z. Galil, S. Haber, and M. Yung. Cryptographic computation: Secure fault-tolerant protocols and the public-key model. In Advances in Cryptology — CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 135–155. Springer-Verlag, 1987.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust and efficient sharing of RSA functions. In Advances in Cryptology — CRYPTO '96, volume 1109 of Lecture Notes in Computer Science, pages 157–172. Springer-Verlag, Aug. 1996.
R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold DSS signatures. In Advances in Cryptology — EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science, pages 354–371. Springer-Verlag, May 1996.
J. A. Garay and Y. Moses. Fully polynomial Byzantine agreement in t + 1 rounds (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 31–41, San Diego, California, May 1993.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game — a completeness theorem for protocols with honest majority. In Proc. 19th ACM Symposium on the Theory of Computing (STOC), pages 218–229, 1987.
R. Gennaro, M. O. Rabin, and T. Rabin. Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In Proc. 17th ACM Symposium on Principles of Distributed Computing (PODC), 1998.
M. Hirt and U. Maurer. Complete characterization of adversaries tolerable in secure multi-party computation. In Proc. 16th ACM Symposium on Principles of Distributed Computing (PODC), pages 25–34, Aug. 1997.
E. Kushilevitz and R. Ostrovsky. Replication is not needed: Single data base computationally-private information retrieval. In Proc. 38th IEEE Symposium on the Foundations of Computer Science (FOCS), pages 364–373, 1997.
E. Kushilevitz. Privacy and communication complexity (extended abstract). In Proc. 30th IEEE Symposium on the Foundations of Computer Science (FOCS), pages 416–421, 1989.
A. Karlin and A. C. Yao. Unpublished manuscript.
L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382–401, July 1982.
F. J. Meyer and D. K. Pradhan. Consensus with dual failure modes. In IEEE Transactions on Parallel and Distributed Systems '91, volume 2, pages 214–221, 1991.
R. J. McEliece and D. V. Sarwate. On sharing secrets and Reed-Solomon codes. Communications of the ACM, 24:583–584, 1981.
T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proc. 21st ACM Symposium on the Theory of Computing (STOC), pages 73–85, 1989.
A. de Santis, Y. Desmedt, Y. Frankel, and M. Yung. How to share a function securely. In Proc. 26th ACM Symposium on the Theory of Computing (STOC), pages 522–533, 1994.
A. Shamir. How to share a secret. Communications of the ACM, 22:612–613, 1979.
A. C. Yao. Protocols for secure computations. In Proc. 23rd IEEE Symposium on the Foundations of Computer Science (FOCS), pages 160–164. IEEE, 1982.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fitzi, M., Hirt, M., Maurer, U. (1998). Trading correctness for privacy in unconditional multi-party computation. In: Krawczyk, H. (eds) Advances in Cryptology — CRYPTO '98. CRYPTO 1998. Lecture Notes in Computer Science, vol 1462. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055724
Download citation
DOI: https://doi.org/10.1007/BFb0055724
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64892-5
Online ISBN: 978-3-540-68462-6
eBook Packages: Springer Book Archive