**Instructor**: Daniele
Micciancio

**Time & Place**: Tu,Th 12:30-1:50pm, Room U413

The lecture of Thu. Nov 7 is rescheduled to Wed. Nov 6 at 2pm in AP&M
4301.

There will be no lecture on Tue. Nov 19.

**Section ID:** 462968

**Prerequisites**: CSE207 (Introduction to cryptography) and
implied prerequisites. It is assumed that all students already have good
knowledge of basic notions from complexity theory and cryptography (e.g.,
pseudorandom generators, pseudorandom functions, private/public key
encryption, digital signatures, message authentication codes, oneway
functions, trapdoor functions, etc.)

**Description**: The main topic of the course is the study of
*secure multiparty computation*, or more generally, complex
cryptographic protogols that go beyond the basic functionalities studied in
the basic course. A useful tool that will be used throughout the course is
zero knowledge proof systems. It is assumed that some (but not all) of the
students might have already studied zero knowledge proof systems in other
(cryptography or complexity) courses. So, this course will give an
introduction to zero knoweldge proofs, but without going through the long
sequence of examples and variations on the theme typical of courses that focus
on ZK proofs. In summary, this course is expected to be accessible to students
without previous knolwedge of ZK proofs, but interesting and informative for
students who already studied ZK proofs in other courses. Depending on the
interest and background of the audience we might also touch some advanced
topics in zero knowledge proofs (e.g., concurrent zero-knowledge, lower bounds
on round complexity, and non black-box zero knoweldge proof systems.)

- Review of basic cryptography and complexity, and brief introduction to zero-knowledge proofs.
- Formulating cryptographic problems as secure multiparty computation
- Oblivious transfer: definitions, constructions, and applications.
- General plausibility results in the computational setting
- General plausibility results in the secure channel setting
- Efficiency issues for generic constructions
- Special cases and applications: e.g. Byzantin agreement, private information retrieval, threshold cryptography
- Definitional issues and composition of secure protocols: Canetti's UC security framework, formulating standard cryptographic primitives within the framework, composition theorems, construction of primitives meeting uc-security
- (Optional) Advanced topics in zero-knowledge: e.g., concurrent zero knowledge, upper and lower bounds on round complexity, black-box vs. non-blackbox zero knolwedge, efficient transformation techniques, etc.
- (Optional) Advanced topics in multiparty computation: e.g., adaptive adversary and deniable encryption, mobile adversaries (proactive security), non-interactive cryptocomputing, etc.

A more detailed list of topics will be posted lecture by lecture below.

Pointers to relevant papers are given at the end of each page below. Most pointers links to pages on ACM or IEEE digital libraries, from which you can easily access additional papers. For a good list of links about secure multyparty computation,

- Introduction to secure multiparty computation (Sep. 26)
- Cryptography and complexity background (Oct. 1)
- Zero Knowledge proof systems (Oct. 3)
- Oblibious Transfer, definition and construction for semihonest parties, (Oct. 8)
- OT: enforcing honest behaviour using Zero Knowledge proofs (Oct. 10)
- (Zero Knowledge) Proofs of knowledge and security for the sender (Oct. 15, 17)
- General definition of secure function evaluation (Oct. 22)
- Composition of secure function evaluation protocols, (Oct. 24)
- Proof of the composition theorem, (Oct. 29, 31)
- Private multiparty computation [GMW], (Nov. 5)
- Secure multiparty computation [GMW], (Nov. 6)
- Private multyparty computation [BGW] (Nov 12)
- Verifiable secret sharing (Nov 14)

Pointers to papers and other reading material are given at the end of each lecture. The complete list of pointers is given below for easy of reference. The list represents only a set of papers that are most relevant for the material presented in these lectures, and is not a comprehensive list of pointers about secure multiparty computation. For a more extended list see see Helger Lipmaa's page.

- S. Goldwasser, Multi party computations: past and present, PODC 1997
- Oded Goldreich, Foundations of
Cryptography, vol. 1 (Basic tools), Cambridge Univ. Press., 2001

(Fragments of a preliminary version of the book are available here.) - O. Goldreich, Secure Multi-Party Computation.
- R. Canetti, Security and Composition of Multiparty Cryptographic Protocols, Journal of Cryptology, 13(1), 2000. (Special issue on secure computation)
- M. Ben-Or, S. Goldwasser, A. Widgerson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, STOC 88