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 |
ANNOUNCEMENTS
- 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.
HOMEWORK
- 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
GRADING AND REQUIREMENTS
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.
READING AND PREREQUISITES
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.