Interactive Proofs, Zero-Knowledge and Secure Computation

Currently offered as CSE 291, Fall 01. Overlaps to some extent with CSE 291 A00, Spring 1998.

Instructor: Mihir Bellare

Lecture time: Tu and Th, 2:20--3:40PM
Lecture location: HSS 2305A

Meetings: I have no official office hour. Students are welcome to drop by. If you want to be sure of catching me, send e-mail to and schedule an appointment.


The first part of the course will be an introduction to zero-knowledge, including interactive proofs; computational and statistical soundness; proofs of knowledge; perfect, statistical and computational zero-knowledge; zero-knowledge proofs for quadratic residuosity; zero-knowledge proofs for NP languages ; applications; witness indistinguishability; composability properties; black-box and non-black-box simulation; brief introduction to concurrent and resettable zero-knowledge. The second part of the course will be an introduction to secure computation, including oblivious transfer; two-party secure function evaluation; multi-party secure function evaluation.


The notion of zero-knowledge is fundamental to modern cryptography. This is less in its role as a ``stand-alone'' tool as in the pervasive, even if not always obvious, presence of the concept. Certainly there is a lot of direct research in the area of zero-knowledge proofs, itself a draw. It would be a mistake, however, to think that zero-knowledge is of interest to you only if you are interested in working in this area. In fact the ideas of zero-knowledge pervade all parts of modern cryptography, and lend a unique and important perspective that deepens your understanding and improves your cryptographic design and analysis skills. Whether you are working on encryption, signatures, identification, key distribution, or even system security, the zero-knowledge perspective can lend insight.

If you are not familiar with the concept, it is not obvious that it is relevant to so much that you are doing. As you understand it better, you start seeing how it is everywhere. The basic idea that an adversary has a ``view,'' and the idea of ``simulating'' this view, is an umbrella under which much of what security is about can be cast.


Pre-requisites: CSE 207, 200, and 202, or permission of instructor.

Auditing: Requires permission of instructor.

Sign-up: Anyone taking or auditing the class should please send me email ( ) so that I can put you on a class mailing list.

Student Requirements: Homeworks.

Homeworks: The materiel here has many subtleties. To get a good understanding, it will not suffice to hear someone lecture about it. You need to get your hands dirty. As a means to this end, I will provide some homework problems. Students are encouraged to think about them, and are asked to turn in solutions to some (to be indicated subset) of them over the course of the quarter. Students may work on homeworks in groups, but the size of the group should be at most two. A group may turn in a common solution.

Related pages at UCSD