COMP 15005
Cryptography
Tufts
University
Spring
2006
Instructor:
Professor Lenore J. Cowen
Office: Halligan Hall 238
Phone: 6176275134 (EMAIL IS PREFERRED: and will average a quicker response)
Email: cowen AT cs.tufts.edu
Office hours: Tuesday 10:3011:30am; Thursday, 1:302:30pm
Teaching Assistants:
Teaching Assistant: Xiangye (Shelly) Li
Email: Xiangye.Li AT tufts.edu
Office hour: Wednesday, 9:30am10:30am
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: 20512315135 2015
31825162015718116825! 208919 62114 31211919
2091212 205138 251521 1915135 156 238120 919
7159147 1514 239208 1311425 156 2085 1615162112118
31825162015718116893
1127151892081319. 4519169205 2085 6151813 156
208919 20512315135, 235 2391212 25
61532119199147 1514 81523 2015 1311215 715154
514318162091514 1938513519, 141520 81523 2015
2185111 214 1514519.
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 DiffieHelman Key Exchange, RSA
PublicKey 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):
 Intro lecture [Jan 19]
 NOVA video [Jan 24]
 Prof. Cowen Lecture [Jan 26] students sign up to lead seminar topics
 Prof. Cowen Lecture [Jan 31]
 Prof. Cowen Lecture [Feb 2]
 Prof. Cowen Lecture [Feb 7]
 Prof. Cowen Lecture [Feb 9]
 NO CLASS (made up at end of semester} [Feb 14]
 Seminar Topic: The Enigma Machine [Feb 16]
Web Readings: UK page
Polish page
photos
Bletchley Park
 Prof. Cowen Lecture [Feb 21]
 NO CLASS THURS FEB 23  TUFTS ON A MONDAY SCHEDULE
 Prof. Cowen Lecture [Feb 28]
 Seminar Topic: Truly Random Bits/Pseudorandom number generators [March 2]
Web readings: Truly random numbers
Nice very simple background essay on randomness and pseudorandomness
RFC 1750
How good is your pseudorandom number generator? Ask NIST!
Modern approach based on 1way functions
 Prof. Cowen Lecture [March 9]
 Prof. Cowen Lecture [March 14]
 Seminar Topic: secret sharing [March 16]
Main reading: Shamir's how to share a secret
Wikipedia article
Bibliography on secret sharing schemes
 SPRING BREAK
 Prof. Cowen Lecture [March 28]
 Seminar Topic: Zero knowledge proofs g [March 30]
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 101111 and 548549 in your Schneier textbook
 Seminar Topic: Electronic voting [April 6] Final project proposals due
Main reading is from your Schneier textbook, pages 125134.
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! :)
 Seminar Topic: Digital Watermarking [April 11]
A simple example of a noncryptographic digital watermark
The problem with noncrpytographic 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
 Seminar Topic: Digital Rights Management [April 13]
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
 Seminar Topic: Trust Management [April 18]
Matt Blaze page see especially his talk slides
The original paper
 Seminar Topic: Clinical trials/medical privacy [April 20]
Example of HIPAA compliance (What is HIPAA? You tell me!)
L. Sweeney HIPAA comments
Latyana Sweeney homepage and her kanonymity paper
Another paper
DIMACS report
IBM Hippocratic Database Project and all the best technical papers are coming out of the same IBM group, follow that link and click on technical papers.
 Seminar Topic: . Electronic cash [April 25]
Read pp. 139147 in your Schneier textbook
Huge collection of weblinks
 Seminar Topic: Cookies and webbugs/spyware and adware [April 27]
Bugnosis
Bugnosis technical paper
Supplementary HW assignment, due April 27th. Download, install and try the Bugnosis software!
 Final project due May 2. No extensions!
Homeworks:
There will be several hw assigments and a final project.
 Due Feb 16: HW 1 (postscript) or pdf

COMP 150 Cryptography, Homework 2, due Thursday, 16 March
Please show your work. You may use a spreadsheet or write a program as long as you give
enough intermediate steps and label them clearly.
 Suppose n = 11303 = 127 * 89 for RSA, and messages are encrypted by raising
them to the e = 5 power mod 11303. Find a power d that can be used for decryption,
encrypt m = 10, and verify that it decrypts correctly.
 When n = p* q (the product of two distinct primes), RSA uses the fact that
a number relatively prime to n raised to the (p1)(q1) power is equal to
1 mod n. This relies on the fact that (p1)(q1) is the Euler totient function,
the number of integers between 1 and n that are relatively prime to n. Find
the Euler totient function if n = p * q * r were the product of three distinct
primes, and show by a numerical example how RSA would encode and decode in
this case.
End of hw2
 Due April 13: HW 3 (postscript) or pdf
 HW4  (optional) due April 27th. Install and try out the bugnosis
software before class on April 27th. Write up a paragraph (to be
handed in April 27th) about what you found.