CS 827: Security and Cryptography

Fall Semester 2001
Instructors:
Manuel Blum  - WeH 4113, x8-3742, mblum@cs.cmu.edu
Nick Hopper (TA)  - WeH 8303, x8-2993, hopper@cs.cmu.edu

Subject

This course will focus on an extremely recent area of research in computer security - Human Interactive Proofs - with the goal of significantly extending the state of the art.  The remainder of the coursework (roughly one-half) will cover some traditional materials from number theory and cryptography.
 

Grading

Grading will be based on periodic homeworks as well as a midterm and a final, dates to be announced.
 

Location

The class meets Tuesdays and Thursdays from 10:30 AM to noon, starting Thursday, September 13.  The meeting location is Wean Hall room 4615A.

Textbook

The recommended textbook for this course is  A Course in Number Theory and Cryptography by Neil Koblitz (ISBN 0387942939; Springer-Verlag).  It can be obtained from Amazon or Barns & Noble. Students interested in learning more about general cryptography might consider consulting one of the following:
Mihir Bellare and Shafi Goldwasser, "Lecture Notes on Cryptography."
Gary and Johnson, "Computers and Intractability: A guide to the theory of NP-completeness."
Hardy and Wright, "An Introduction to the Theory of Numbers."
William J. LeVeque, "Fundamentals of Number Theory."
Michael Luby, "Pseudorandomness for Cryptographic Applications."
Menezes, van Oorschot, and Vanstone, "Handbook of Applied Cryptography."

Prerequisites

Students should have some background in algorithms and computational complexity, e.g. 15-451. Students may find it useful to have some background in number theory, computer systems, or cognitive psychology.
 

Class Notes

Lecture 1 - Class Overview.
Lecture 2 - HumanOIDS.
Lecture 3 - Definitions, Homework 2. (Answer key for Homework 2)
Lecture 4 - Factoring and Machine Learning.
Lecture 5 - PhoneOIDS protocols.  (Homework 3)
Lecture 6 - Formal Definitions for PhoneOIDS.
Lecture 7 - Parity with Noise.
Lecture 8 - Midterm Review.
Lecture 9 - Chosen Challenge Security.  (The Hunting of the Snark)
Lecture 10 - Midterm Review 2 - Assignment 4.
Lecture 11 - Midterm assignment.
Lecture 12 - CAPTCHA.
Lecture 13 - PhonOIDS and The 1/p generator.
Lecture 14 - PhonOIDS #82.
Lecture 15 - PhonOIDS #82.
Lecture 16 - CAPTCHA and the image recognition problem.
Lecture 17 - ASCII CAPTCHAs.
Lecture 18 - More on ASCII CAPTCHAs.
Lecture 19 - On the (im)possibility of ASCII CAPTCHAs.
Lecture 20 - Infeasibility of some ASCII CAPTCHAs.