CSE208: Advanced cryptography, Fall 2002

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

Course Outline

  1. Review of basic cryptography and complexity, and brief introduction to zero-knowledge proofs.
  2. Formulating cryptographic problems as secure multiparty computation
  3. Oblivious transfer: definitions, constructions, and applications.
  4. General plausibility results in the computational setting
  5. General plausibility results in the secure channel setting
  6. Efficiency issues for generic constructions
  7. Special cases and applications: e.g. Byzantin agreement, private information retrieval, threshold cryptography
  8. 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
  9. (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.
  10. (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.

Lectures

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,

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

Assignments

Calibration homework (ps,pdf)

Homework Assignment (ps,pdf)

References

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.