Introduction to secure computation

The objective of this paper(1) is to give an elementary introduction to fun damental concepts, techniques and results of Secure Computation, Topics covered include classical results for general secure computation by Yao, Goldreich & Micali & Wigderson: Kilian. Pen-Or & Goldwasser Sr Wigders on, and Chaum & Crepeau & Damgaard. We also introduce such concepts as oblivious transfer: security against mal icious attacks and verifiable secret sharing, and for some of these importa nt primitives we discuss realization, This paper is organized as follows. Part I deals with oblivious transfer and secure (general) two-party computa tion. Part II discusses secure general multi-party computation and verifiable sec ret sharing, Part III addresses information theoretic security and presents detailed but elementary explanations of some recent results in Verifiable Secret Sharin g and Multi-Party Computation. The importance of theory and general techniques often lies in the fact that the true nature of security is uncovered and that this henceforth enables to explore what is "possible at all". This then motivates the search for co ncrete and often specialized realizations that are more efficient, Neverthe less, many principles developed as part of the general theory are fundament al to the design of practical solutions as well.