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 mihir@cs.ucsd.edu and schedule an
appointment.
Topics
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.
Motivation
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.
Requirements
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 ( mihir@cs.ucsd.edu ) 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