15-503/15-859P Introduction to Theoretical Cryptography


Spring 2006, MW 3:00-4:20, Wean 5409

Note this course has two numbers: an undergraduate and graduate number, respectively.

Instructors:
Manuel Blum, Wean 4113. Office Hours: After Class
Steven Rudich, Wean 7128. Office Hours: MW 2pm-3pm, Starbucks at Fifth and Craig
TA: Ryan Williams, Wean 4112. Office Hours: Thursday 3-4pm

This course provides a serious introduction to theoretical cryptography. We will cover definitions of basic concepts such as one-way functions, pseudorandom generators, pseudorandom functions, encryption, etc. We will also cover some basic number theory. Although this is a theory course, it will not be just a course of abstract definitions: we will strive to make things as concrete as possible.


Textbook: None-- we will occasionally provide links to lecture notes and readings.

Prerequisites: For undergraduates, 15-451 (15-453 is also recommended).

Grading (Tentative):
Homework, 10%
Two Midterms (One In-Class, One Take-Home), 20% each
Final Exam (In-Class), 25%
Final Project/Presentation, 25%.

Attendance is required.

 Homework: Homework is due one week after it is assigned. Late homework will be accepted only under exceptional circumstances. Each student is to do their own work and hand in their own homeworks individually. If you must, you may use any other sources you like, without losing points, provided that on each HW you turn in, you declare honestly where the major ideas came from. This could be: yourself, someone else, Google-- all possiblities are okay provided you declare honestly how you got the ideas.
Project/Presentation: You will be given the choice to do either a final project, or a short presentation on a topic of your choice (approved by us).

Tentative List of Topics

  1. Zero-Knowledge: Hamilton Cycle, Graph isomorphism, Etc.
  2. One-Way Functions. Bit Commitment.
  3. Some Number Theory: Extended GCD, Continued Fractions, Quadratic Residues, Chinese Remainder Representation, Prime Number Theorem, Twin Primes Conjecture, Euler totient function.
  4. Primality versus Factoring. AKS Deterministic Primality Test.
  5. Discrete logarithm: applications to double-lock encryption, coin flipping over the telephone.
  6. Oblivious Transfer.
  7. Bit by bit exchange of secret keys.
  8. Pseudorandomness.
  9. Secure Multi-Party Computation.

© 2005-2006 Carnegie Mellon University, all rights reserved.