• Kolmogorov axioms for probability theory, Measures on oracles, Caratheodory Extension theorem, Borell-Cantelli, RO is non-uniformly one-way (th)
  • Taxonomy of reductions (cb)
  • Overview of important black-box and non-black-box construction (rp)

Classical Topics:

  • Optimal attacks in the random-oracle model on KA and DS schemes (mm)
  • Power of non-uniformity in black-box separations (mm)
  • Gennaro-Trevisan, basic compression result and applications (ih)
  • Tight Lower Bounds on the Round Complexity and Communication Complexity of Statistically Hiding Commitments (HHRS) (ih)
  • On the Instantiability of Hash-and-Sign RSA Signatures (DHT) (ih)
  • Lower bound on PRG from OWF (th)

Complexity-Theoretic Topics:

  • Complexity theoretic foundations: NP, AM, SZK (ab)
  • Worst-case vs. average-case, randomness and proofs, Feigenbaum-Fortnow (ab)
  • Complexity aspects of homomorphic encryption (ab)
  • Program checkers (mm)


  • Impossibility results for zero-knowledge (rp)
  • Impossibility results for non-black-box constructions (meta-reductions) (rp)
  • Meta-reductions and DS schemes (mf)

Possible Discussion

  • Barriers (all)