BRICS Course on Secure Multi-Party Computation

A PostScript version of this document is available.

Contents

The problem of secure multi-party function computation is as follows: n players, wish to evaluate a function , where is a secret value provided by . 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).

Lecture 1: Private Computation Protocols

Lecture 2: Secure Computation Protocols

Lecture 3: Handling more faults and other topics

Schedule

The course and lectures on Secure Multi-Party Computation will take place at the Department of Computer Science, University of Aarhus, the 24 and 25 August 1995.

Literature

The main references for the lectures are [BOGW88,CCD88,RBO89,Bea91]. Note however that the protocols that will be presented in the lectures will be much simpler than those that have appeared in the original papers.

Additional references include [BOCG93,MOKR94] for asynchronous computations, [BIB89,BFKR91,FY92,FKN94] for round and communication complexity, [DDWY93,Dwo92] for partial networks and VSS. References for t-private computation for include [Kus92,CK91,BYCKO93,CK93b,CK93a,CGGK94,KMO94,KR94,CGGK95,CS95].

References

Bea91
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.

BIB89
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.

BOCG93
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.

BOGW88
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.

BYCKO93
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.

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

CGGK95
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.

Dwo92
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.

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

MOKR94
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.

RBO89
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

The course and lectures are open to all. BRICS can assist in arranging accommodation, and possibly with local expenses in a few needy cases. For further information and to register your attendance, please contact BRICS@brics.aau.dk.