CS4261: Introduction to Cryptography
Spring 2007
Instructor: Professor Michael Rabin
Office Hours: Tuesdays, 2:00-3:00PM 502 CSB

Teaching Assistants:

Seung Geol Choi
sc2506 at cs dot columbia dot edu
511 CSB
Office Hours: Wednesdays 12:30-2:30PM
Andrew Wan
atw12 at columbia dot edu
516 CSB
Office Hours: Mondays 3:00-5:00PM

  • Class is held in 1127 MUDD.
  • Lectures can be viewed here from an on campus computer.
  • The first algebra discussion section was held Friday, January 26, 2:00pm in 633 Mudd. The notes from this lecture can be downloaded here.
  • The second algebra section was held Friday, February 2, 2:00pm in 633 Mudd. The notes from this lecture can be downloaded here.
  • The following books are recommended for the student that wants more material in algebra and number theory:
    • V. Shoup. A Computational Introduction to Number Theory and Algebra.
      An excellent source, written with cryptographic applications in mind.
    • D. Angluin: Lecture Notes on the Complexity of Some Problems in Number Theory.
      Available for download here (pdf) or here (ps).
    • L.N. Childs: A Concrete Introduction to Higher Algebra.
      An accessible reference to algebra and number theory, with many cryptographic applications.
  • The "Handbook of Applied Cryptography" is now available on reserve at the Engineering Library.
  • "A Concrete Introduction to Higher Algebra" is available on reserve at the Mathematics Library.
  • The zero knowledge review will was held Friday, Mar 2 and is available for viewing via cvn.
  • The handout from class.
  • The handout on Paillier Encryption.
  • The final exam will be on Tuesday, May 8, from 9:00-12:00 in room 535 Mudd.

OVERVIEW The following topics will be covered. Emphasis will be on developing cryptographic skills and understanding.
  • Modern cryptography: Computer and network security, e-commerce and privacy protection all employ cryptography.
  • Tools: Primality testing, finite fields, basic number theory.
  • Algorithms and protocols: Public-key encryptions, digital signatures, key exchanges, authentication, commitments, zero knowledge proofs, oblivious transfer, secret sharing, distributed agreements, homomorphic encryptions, applications to e-voting and secure auctions.
  • Foundations: Probabilistic encryptions, semantic security.
  • Attacks and countermeasures.
  • Absolutely secure encryptions.

  • hw1 due Tuesday, January 30
  • hw2 due Thursday, Feb 8
  • hw3 due Tuesday, Feb 27
  • hw4 due Tuesday, Apr 10
  • hw5 due Tuesday, Apr 24


Coursework will consist of six problem sets, a midterm, and a final exam. The homework counts for 30% of your final grade, the midterm for 25%, and the final exam for 45%. Students are encouraged to work in groups to solve problems, but solutions must be written individually.


The only prerequisite is mathematical maturity; background knowledge of algebra and number theory is helpful, but all the necessary material will be covered in class.

There is no required textbook for the course. The following book is recommended as a supplemental text:
Handbook of Applied Cryptography
by Alfred J. Menenzes, Paul C. van Oorschot, and Scott A. Vanstone.
CRC Press, Inc

The book is also available online here.