COMP 150-05
Cryptography
Tufts
University
Spring
2006
Professor Lenore J. Cowen
Office: Halligan Hall 238
Phone: 617-627-5134 (EMAIL IS PREFERRED: and will average a quicker response)
Email: cowen AT cs.tufts.edu
Office hours: Tuesday 10:30-11:30am; Thursday, 1:30-2:30pm
Teaching Assistants:
Teaching Assistant: Xiangye (Shelly) Li
Required Text Book:
Applied Cryptography, by Bruce Schneier, 2nd Edition.
John Wiley and Sons, 1996.
Note: this course is also open to math majors without substantial Computer Science coursework
About the course: 20-5-12-3-15-13-5 20-15
3-18-25-16-20-15-7-18-1-16-8-25! 20-8-9-19 6-21-14 3-12-1-19-19
20-9-12-12 20-5-1-3-8 25-15-21 19-15-13-5 15-6 23-8-1-20 9-19
7-15-9-14-7 15-14 23-9-20-8 13-1-14-25 15-6 20-8-5 16-15-16-21-12-1-18
3-18-25-16-20-15-7-18-1-16-8-9-3
1-12-7-15-18-9-20-8-13-19. 4-5-19-16-9-20-5 20-8-5 6-15-18-13 15-6
20-8-9-19 20-5-12-3-15-13-5, 23-5 23-9-12-12 2-5
6-15-3-21-19-19-9-14-7 15-14 8-15-23 20-15 13-1-121-5 7-15-15-4
5-14-3-18-16-20-9-15-14 19-3-8-5-13-5-19, 14-15-20 8-15-23 20-15
2-18-5-1-11 2-1-4 15-14-5-19.
Class Structure: This class will teach you some
of what's going on behind many of the popular cryptographic
algorithms. Because the class has a big independent project component,
it is easy to delve deeply into the parts of the topic that interest
you! The first month will be mostly lectures; we will
introduce the algorithms behind Diffie-Helman Key Exchange, RSA
Public-Key Encryption, and Digital Signatures, developing the mathematics we need as we go to
understand both the algorithms and the hardness assumptions and
delicate issues in their practical implementation. In the second 2/3
of the class, we will devote half the class period to a more "seminar"
format, where a set of readings will be assigned the previous week on
a special topic, all students will be responsible for reading the
papers; but a pair of students will be in charge of leading the
discussion on that topic in class based on the readings.
This class also has a substantial independent project component. Start
thinking about what you want to do your project early; a formal
project proposal is due the week after Spring break (March 30), and the final
project itself is due May 2. There will be no extensions on the
due date for the final project.
Special Topic Dates (and Readings):
Email: Xiangye.Li AT tufts.edu
Office hour: Wednesday, 9:30am-10:30am
Web Readings: UK page
Polish page
photos
Bletchley Park
Web readings: Truly random numbers
Nice very simple background essay on randomness and pseudorandomness
RFC 1750
How good is your pseudo-random number generator? Ask NIST!
Modern approach based on 1-way functions
Main reading: Shamir's how to share a secret
Wikipedia article
Bibliography on secret sharing schemes
From wikipedia, with good simple examples
Oded Goldreich's tutorial; a fantastic resource
Techincal: the original paper that shows you can prove NP in zero knowledge by Goldreich, Micali and Widgerson
Read pages 101-111 and 548-549 in your Schneier textbook
Main reading is from your Schneier textbook, pages 125-134.
Rebecca Mercuri page on electronic voting
Good collection of links from Ron Rivest
ACM project
A few cute pictures,but don't base your presentation on this! :-)
A simple example of a non-cryptographic digital watermark
The problem with non-crpytographic watermarks is they are too easy to detect and/or too easy to remove. We want to watermark our copyrighted image in such a way that the (visible or invisible) watermark is either hard to detect or hard to remove without changing the entire image so that we can still prove we own the image if someone tries to publish it or modify it. In some circumstances we want a visible watermark in others, the protection against removal of the watermark is that it is undetectable, i.e. no one would even suspect it was there. In this second case, the problem is sometimes also called steganography.
Wikipedia link
A good student survey/introduction
A second student survey
One of the many comercial companies, Digimark
Steganography links
A simplistic scheme
A modern cryptographic approach
Yet another paper
Large list of weblinks
Wikipedia has a very good entry on this topic
A timely link to the SONY 2005 controversy, also from wikipedia
Links from the WWW Virtual Library
Read this paper!
The PORTIA project
Matt Blaze page see especially his talk slides
The original paper
There will be several hw assigments and a final project.