last reading assignment (for 11/1 and 18/1)

[עודד גולדרייך‎]

A LAST READING ASSIGNMENT

This assignment is intended for the last two meeting of this semester,
which will take place on 11 and 18th of Jan 2011.
The material is Sec 4.4, which is devoted to the construction
of zero-knowledge proof systems for any set in NP.
After seeing the abstract outline of this proof system,
you will be well motivated to learn a new tool --
commitment schemes (in Sec 4.4.1). Next, turn to the
digital implementation of the ZKIP for NP (in Sec 4.4.2),
and finally to the generic application (in Sec 4.4.3).

I suggest to skip some deatils in the first reading,
so that we can discuss higher level issues already
on 11/1/11, and get to all details only after that.


PARTIAL ANSWER TO A QUESTION RAISED IN TODAYS MEETING

The question refered to statistical zero-knowledge
under the bare definition (i.e., without auxiliary-inputs).
It was asked whether this definition can be seperated from
auxiliary-input statistical zero-knowledge.
While I suspect so, I still don't know the answer.
However, I know that this definition is *partially*
closed under sequential composition: specifically,
sequentially executing any statistical zero-knowledge protocol,
for any *constant* number of times, yields a statistical
zero-knowledge protocol. I think that a larger number of
sequential executions may violate the zero-knowledge condition,
but I may be wrong.

[עודד גולדרייך‎]

Hi all.

Next week we shall meet for the last time this semester;
the reading assignment is as in last time, but this time
you are asked to read more carefully and pay attention to
all details (except really minor/annoying ones...).

The next meeting will be devoted to this material as well as to
any other questions/issues you may raise re all that you read
and/or all that appears in the first volume.

Oded