Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >IPEC Summer 2007 

Student Wish Course


Prof. Dr. Joachim von zur Gathen


Michael Nüsken

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.


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


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.



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.


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.



There are 20 places.


The course will be held in English.

Imprint, webmaster & more