Secure Multi-Party Computation

Course Contents

The problem of secure multi-party function computation is as follows: n players, P₁,...,P_n wish to evaluate a function F(x₁,...,x_n), where x_i is a secret value provided by P_i. The goal is to preserve the privacy of the player's inputs and guarantee the correctness of the computation. This problem is trivial if we add a trusted third party T to the computation. Simply, T collects all the inputs from the players, computes the function F, and announces the result. (This is the way we usually have elections, where the voters are the players and the trusted third party is the government). In general, we define secure multiparty computation as any protocol in an ideal scenario with a ``trusted party'', and define a real life protocol as secure if it is ``equivalent'' to a computation in the ideal scenario.

We show that whatever can be computed in this ideal scenario can be computed in a secure manner when no such trusted party exists. We consider two types of ``faulty'' behaviour by the players. First we assume that players always follow the protocol but may collaborate and try to learn additional information (private computation), and the general case where faulty players can collaborate in any way to gather information and disrupt the computation (secure computation).

Programme

Thursday August 24, 1995, 10:15-12:00 in Auditorium D4

Private Computation Protocols

• The Trusted Third Party model and formal definitions of t-private and t-secure protocols.
• Secret sharing protocols.
• The main Theorem: For t<n/2, any function can be computed t-privately.
• Survey (and if time permits some proofs) of the known results about t-private computation for t >= n/2.

Thursday August 24, 1995, 14:15-16:00 in G31

Secure Computation Protocols

• Verifiable secret sharing protocols (VSS).
• Verifiable secret computation.
• The main Theorem: For t<n/3 any function can be computed t-securely.

Friday August 25, 1995, 10:15-12:00 in Auditorium D4

Handling more faults and other topics

• The Information Checking Protocol.
• t-secure verifiable secret sharing for t<n/2, and as a corollary we prove: For t<n/2 any function can be computed t-securely (with exponentially small probability of error).
• Further results (as time permits) will include: Secure computation in partial communication networks; The communication and round complexity of private protocols; and a survey of the known results on asynchronous secure computation.

References

Additional references include [BOCG93,BKT94] for asynchronous computations, [BB89,BFKR91,FY92,FKN94] for round and communication complexity, [DDWY93,D92] for partial networks and VSS. References for t-private computation for t >= n include [K92,CK91,BCKO93,CK93a,CK93b,CGK94,KMO94,KR94,CGK95,CS95].

[B91]

Beaver. Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology, 4:75-122, 1991.

[BFKR91]

D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway. Security with low communication overhead. In A. J. Menezes and S. A. Vanstone, editors, Proc. CRYPTO 90, pages 62-76. Springer-Verlag, 1991. Lecture Notes in Computer Science No. 537.

[BB89]

Bar-Ilan and Beaver. Non-cryptographic fault-tolerant computing in a constant number of rounds of interaction. In 8th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 1989.

[BCG93]

M. Ben-Or, R. Canetti, and O. Goldreich. Asynchronous secure computation. In Proc. 25th ACM Symposium on Theory of Computing (STOC), pages 52-61, 1993.

[BGW88]

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proc. 20th Ann. ACM Symp. on Theory of Computing, pages 1-10, 1988.

[BCKO93]

Bar-Yehuda, Chor, Kushilevitz, and Orlitsky. Privacy, additional information, and communication. IEEE Transactions on Information Theory, 39, 1993.

[CCD88]

D. Chaum, C. Crepeau, and I. Damgård. Multi-party unconditionally secure protocols. In Proc. 20th ACM Symp. on Theory of Computing, pages 11-19, Chicago, 1988. ACM.

[CGK94]

Chor, Gereb-Graus, and Kushilevitz. On the structure of the privacy hierarchy. Journal of Cryptology, 7, 1994.

[CGK95]

Chor, Gereb-Graus, and Kushilevitz. Private computations over the integers. SIAM Journal on Computing, 24, 1995.

[CK91]

B. Chor and E. Kushilevitz. A zero-one law for Boolean privacy. SIAM J. Disc. Math., 4:36-47, 1991.

[CK93a]

Chor and Kushilevitz. A communication-privacy tradeoff for modular addition. Information Processing Letters, 45, 1993.

[CK93b]

Chor and Kushilevitz. Secret sharing over infinite domains. Journal of Cryptology, 6, 1993.

[CS95]

Chor and Shani. The privacy of dense symmetric functions. Computational Complexity, 5, 1995.

[DDWY93]

Danny Dolev, Cynthia Dwork, Orli Waarts, and Moti Yung. Perfectly secure message transmission. Journal of the ACM, 40(1):17-47, January 1993.

[D92]

Cynthia Dwork. On verification in secret sharing. In J. Feigenbaum, editor, Proc. CRYPTO 91, Lecture Notes in Computer Science No. 576, pages 114-128, Springer, 1992.

[FKN94]

Feige, Kilian, and Naor. A minimal model for secure computation (extended abstract). In ACM Symposium on Theory of Computing (STOC), 1994.

[FY92]

M. Franklin and M. Yung. Communication complexity of secure computation. In Proc. 24th ACM Symposium on Theory of Computing (STOC), pages 699-710, 1992.

[KMO94]

Eyal Kushilevitz, Silvio Micali, and Rafail Ostrovsky. Reducibility and completeness in multi-party private computations. In Proc. 26th ACM Symp. on Theory of Computing, pages 478-489, Santa Fe, 1994. IEEE.

[KR94]

Eyal Kushilevitz and Adi Rosén. A randomnesss-rounds tradeoff in private computation. In Yvo G. Desmedt, editor, Proc. CRYPTO 94, Lecture Notes in Computer Science No. 839, pages 397-410. Springer, 1994.

[K92]

Kushilevitz. Privacy and communication complexity. SIAM Journal on Discrete Mathematics, 5, 1992.

[BKT94]

M.Ben-Or, B. Kelmer, and T. Rabin. Asynchronous secure computation with optimal resilience. In Proc. 13th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 1994.

[RB89]

T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proc. 21th ACM Symposium on Theory of Computing (STOC), pages 73-85, 1989.

Registration