• Offered at...
  • Department of Computer Science and Information Engineering, National Taiwan University, Spring, 2003
• Instructor:
  • Prof. Hsueh-I Lu
• Time and place:
  • 1-4pm, Tuesday. Classroom: Room 101, Building of Common Courses, NTU.
• Prerequisites:
  • Basic knowledge of algorithms, computability, and elementary probability theory.
  • Background on (computational) number theory is welcome but not required.
• We will investigate the theoretical foundations of cryptography from the viewpoint of computational difficulty. The outline is as follows.
  • Introductions
  • One-way functions and computational difficulty
  • Pseudorandom generators
  • Zero-knowledge proofs
• Textbook:
  Foundations of Cryptography - Basic Tools, by Oded Goldreich, Cambridge University Press, 2001. (ISBN 0-521-79172-3)
• Scribed notes
  • Tzhua Chen's Scribe notes are here.
• Midterm exam
  • problem set: (ps and pdf).
  • solution: word doc.
  • grade (updated on July 1, 2003): html.
• Final exam
  • problem set: (ps and pdf).
  • solution: p1 p2 p3 p4.
  • grade (updated on July 3, 2003): html.
• Final grades
  • here. (posted on July 10, 2003)
• Mailing list:
  • Join the mailing list called 'crypto-ntu@coollist.com'
    • by filling out this form, and you will receive the broadcasting messages of this course.
    • No need to be serious about those questions asked during your registration to this mailing list. Just filling in something random. I won't be able to access those information.
• Final presentation.
• Possible papers for final presentation
  • The Provable Security of Graph-Based One-Time Signatures and Extensions to Algebraic Signature Schemes, by Alejandro Hevia and Daniele Micciancio, ASIACRYPT 2002.
  • Indistinguishability of Random Systems, Ueli Maurer, EUROCRYPT 2002.
  • Efficient dynamic traitor tracing, by Omer Berkman, Michal Parnas and J. Sgall, SODA 2000.
  • Efficient Traitor Tracing Algorithms Using List Decoding, by Alice Silverberg, Jessica Staddon, and Judy L. Walker, ASIACRYPT 2001.
  • Watermarking Maps: Hiding Information in Structured Data, by Sanjeev Khanna and Francis Zane, SODA 2000.
  • Efficient Amplification of the Security of Weak Pseudo-random Function Generators, by Steven Myers, EUROCRYPT 2001.
• Interesting URLs:
  • The complexity zoo
  • Lance Fornow's Complexity Log
  • a course at BRICS
  • A compendium of NP optimization problems.
  • Theory of Cryptography Conference (TCC)
  • Crypto 2003
  • Asiacryp 2003

Number of accesses since November 1, 2002.
FastCounter by bCentral