Student Wish Course

Responsible

Lecturer

Time & Place

Choosen time: 6 - 10 August 2007 (week 32)
Each day will be 9.00 to 17.00 with two hours of breaks.
Start: Monday at 9.00 in the b-it entrance hall.

Exam

The exam will be on a date to be fixed in the
course.

Allocation

The course is equivalent to 2+1 SWS, and may earn you 4 credits. Media Informatics: Computer and Communication Technology
Recommendation for University of Bonn - Computer Science: A or A1, respectively.

PRG

Pseudo random generation form a basis of virtually all (public key) cryptosystems. If keys are not chosen at random the system can be attacked at that point. In order to be able to evaluate the security we need a thorough definition. It turns out that there are two: (i) the bit sequence produced should computationally be indistinguishable from a random bit sequence, and (ii) the next bit of the generator should not be computationally predictable. Yao's theorem says that the two notion are asymptotically equivalent. And we'll need the notion of computational indistinguishability for zero knowledge.

ZK

Zero knowledge is a property of a protocol. If, say, you want to prove that you have the solution of some very difficult problem then you may of course just hand the solution to convince any verifier. But can you at the same time keep the solution secret? Such a protocol may be used to authenticate someone, he just proves that he knows the secret key of some public key known to the verifier.

PCP [if we find the time and interest]

Probabilistically checkable proofs are a further step. Given a formal proof it is usually easy to check it. But what if the proof is very, very long? Say, you can only look at log(n) bits though the proof has n bits. Can you still get a suitable conviction that the proof is true? This kind of constructions turned out to be very important for complexity theory. Lots of connections between various complexity classes (P, NP, and so on) became visible.

Materials

Oded Goldreich (2001), Foundations of Cryptography . Volume 1: Basic Tools. (See also Fragements of a book .)
Oded Goldreich (2004), Foundations of Cryptography . A Primer.
Oded Goldreich & Avi Wigderson (2004), Computational Complexity . (A Survey.)
Oded Goldreich (2007+), Computational Complexity: A Conceptual Perspective . Drafts of a book.
Wikipedia (2007), The Blum Blum Shub generator .
You also find a pointer to the first publication in CRYPTO'82 there.
Michael Nüsken (2007). Mixed notes from the class.
Wikipedia (2007), PCP .
Wikipedia (2007), PCP theorem .

Participants

There are 20 places.

Language

The course will be held in English.