Course Contents
The problem of secure multiparty function computation is as follows:
n players, P_{1},...,P_{n} wish to evaluate a function
F(x_{1},...,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).
References
The main references for the lectures are
[BGW88,CCD88,RB89,B91]. 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,BKT94] for asynchronous
computations, [BB89,BFKR91,FY92,FKN94] for round and
communication complexity, [DDWY93,D92] for partial networks
and VSS. References for tprivate computation for t >= n include
[K92,CK91,BCKO93,CK93a,CK93b,CGK94,KMO94,KR94,CGK95,CS95].
 [B91]

Beaver.
Secure multiparty protocols and zeroknowledge proof systems
tolerating a faulty minority.
Journal of Cryptology, 4:75122, 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 6276. SpringerVerlag, 1991.
Lecture Notes in Computer Science No. 537.
 [BB89]

BarIlan and Beaver.
Noncryptographic faulttolerant computing in a constant number of
rounds of interaction.
In 8th ACM SIGACTSIGOPS Symposium on Principles of Distributed
Computing, 1989.
 [BCG93]

M. BenOr, R. Canetti, and O. Goldreich.
Asynchronous secure computation.
In Proc. 25th ACM Symposium on Theory of Computing (STOC),
pages 5261, 1993.
 [BGW88]

M. BenOr, S. Goldwasser, and A. Wigderson.
Completeness theorems for noncryptographic faulttolerant
distributed computation.
In Proc. 20th Ann. ACM Symp. on Theory of Computing, pages
110, 1988.
 [BCKO93]

BarYehuda, 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.
Multiparty unconditionally secure protocols.
In Proc. 20th ACM Symp. on Theory of Computing, pages
1119, Chicago, 1988. ACM.
 [CGK94]

Chor, GerebGraus, and Kushilevitz.
On the structure of the privacy hierarchy.
Journal of Cryptology, 7, 1994.
 [CGK95]

Chor, GerebGraus, and Kushilevitz.
Private computations over the integers.
SIAM Journal on Computing, 24, 1995.
 [CK91]

B. Chor and E. Kushilevitz.
A zeroone law for Boolean privacy.
SIAM J. Disc. Math., 4:3647, 1991.
 [CK93a]

Chor and Kushilevitz.
A communicationprivacy 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):1747, 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 114128,
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 699710, 1992.
 [KMO94]

Eyal Kushilevitz, Silvio Micali, and Rafail Ostrovsky.
Reducibility and completeness in multiparty private computations.
In Proc. 26th ACM Symp. on Theory of Computing, pages
478489, Santa Fe, 1994. IEEE.
 [KR94]

Eyal Kushilevitz and Adi Rosén.
A randomnesssrounds tradeoff in private computation.
In Yvo G. Desmedt, editor, Proc. CRYPTO 94,
Lecture Notes in Computer Science No. 839, pages 397410.
Springer, 1994.
 [K92]

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

M.BenOr, B. Kelmer, and T. Rabin.
Asynchronous secure computation with optimal resilience.
In Proc. 13th ACM SIGACTSIGOPS Symposium on Principles of
Distributed Computing (PODC), 1994.
 [RB89]

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