Professor: Jill Pipher
Office: 214 Kassar-Gould House
Phone: (401) 863-3323
Fax: (401) 863-9013
Email: jpipher at math.brown.edu
Office Hours: Tues. 10:30-12, Wed. 2-3, and by appt.
The course will focus on public key cryptography and its applications,
but will include topics in symmetric ciphers, protocols and
complexity . Grades in the course are based on
weekly homework assignments (10%), one midterm (25%) the final examination
(40%) and a final project (25%). The project will involve writing a short
paper on a topic of interest not covered in the class. The syllabus and
assignments will be posted on
this website, and updated
weekly. All homework assigned during a
given week is due on Thursday of the following week.
Who should take this course? This course has no advanced prerequisites,
but I'll assume you've had (or are taking now)
a course in linear algebra (52 or
54). The course is self contained, and is appropriate as a first upper division
mathematics course. More advanced students should plan on reading
some of the papers in the optional reading list below, and find a more
challenging final project.
Some information about the final project:The final project is 5-6 page
paper on a topic of your choice, not covered (or not covered completely)
in class. You will choose a topic, of importance in cryptography, do
some independent reading, and write up your understanding of the subject
in a short expository paper. The paper should include your solution
of a particular problem in that subject - like an exercise illustrating
the ideas, or an original example. All sources should be cited.
You may work with someone else - then your paper will be 10-12 pages long.
I'll make some suggestions of possible topics, but this is your
chance to explore something that interests you.
For example, there are plenty of projects
that involve coding and running experiments, if that's where your interests
lie.
Extra help in math 158: We are fortunate to have
an undergraduate TA for this course, who will be holding a weekly
recitation section. The recitation section is optional, not
mandatory, but I recommend that you attend if possible.
Your TA is Danny Scheinerman
and you can contact him by email at
Daniel_Scheinerman@Brown.edu
The recitation section is Wed. evening 7:30-8:30
in Barus-Holley 153.
Undergraduates with an interest or major in mathematics can check out the
Mathematics Department undergraduate program website at
http://www.math.brown.edu/ugrad_prog.html and the
links there to the Math DUG and
WISE (Women in Science
and Engineering) groups.
OPTIONAL READING:
I'll update this from time to time. If you have suggestions, or readings
you'd like to see here, let me know.
Here's a nice short bio of Claude Shannon:
Claude Shannon, 1916-2001, by R. Calderbank and N. Sloane
New Directions in Cryptography, Diffie & Hellman
The Rise and Fall of Knapsack Cryptosystems, A. Odlyzko
Advanced students will find technical information and downloadable
articles on Ntru at
http://www.ntru.com/cryptolab/. There are also tutorials on modular
arithmetic, polynomials, and Ntru examples available at this site.
Twenty years of attacks on RSA, by Dan Boneh
A Tale of Two Sieves, by C. Pomerance,
PRIMES is in P, by M. Agrawal, N. Kayal, and N. Saxena
Here is an article by Dorit Aharonov on quantum computing and its
connection to problems of interest to cryptographers. This is not
a subject we'll be covering in class, but future cryptographers and advanced
students looking for project ideas should take a look.
Quantum Computing, by D. Aharonov
Here are some notes from the guest lecture on
October 7.
One dimensional NTRU, by J. Hoffstein
| Calendar | Material Covered | Homework Assignments |
| Sept. 4 | Introduction, basic modular arithmetic and
Euclidean algorithm: 1.1 - 1.3 | Read 1,1-1.3, p.47 #1.1(b), 1.5(a), 1.6, 1.9(a),(b),
1.16(f),(g), 1.17(b),(e), 1.23(a), |
| Sept. 9
Sept. 11 | Fast exponentiation, Symmetric ciphers
Discrete logs and Diffie-Hellman | Read 1.4-1.7
p.47 #1.28(a), 1.30(b), 1.31(b), 1.32(d), 1.34(a),(b)(ii), 1.42(a), 1.45, 1.47(a),(c) p. 105 2.3, 2.4(a), |
| Sept. 16
Sept. 18 | El-Gamal, chosen ciphertext attack, Intro to groups
Lagrange's theorem , order notation, Diffie-Hellman in different groups, birthday paradox | p.105 #2.6, 2.8, 2.15
p. 105 #2.10, #2.16(d)(e), |
| Sept. 23
Sept. 25 | Collision algorithms,Chinese Remainder,
Pohlig-Hellman, | p. 105, #2.17(a),(b) - part (b) is optional, 2.19. 2.23(a),(d)
p.105, 2.24, 2.25, 2.27 |
| Sept. 30
Oct. 2 | Examples and worked problems, Rings and fields
Euler's Formula, RSA | None for Tuesday
p.176 #3.1(c), 3.2,3.5(a),3.6,3.8(a),3.10 |
| Oct. 7
Oct. 9 | N=1 case of NTRU (notes are posted above)
Factoring: finding primes, Miller-Rabin | p.176 #3.13(a),(c), 3.14(a),(d), 3.18(a)
|
| Oct. 14
Oct. 16 | Factorization algorithms
Begin chapter 4 | #3.21, 3.22(a)-(e), 3.23(d),3.25(c)
Read section 4.2 #4.7, 4.8, 4.19(a),(b), 4.21 |
| Oct. 21
Oct. 23 | More on probability, Bayes formula, expected value
Collision algorithms/meet-in-the-middle | #4.29, 4.32,
#4.37, 4.38 |
| Oct. 28
Oct. 30 | Midterm Exam
Subset sum problem, knapsacks | #6.2(c),(d), 6.5, 6.6
|
| Nov. 4
Nov. 6 | Lattices: basic defintions
SVP, CVP: Gauss's algorithm in 2-d | #6.7, 6.10, 6.11, 6.13
Start exploring topics for final project |
| Nov. 11
Nov. 13 | Minkowski's theorem, Gaussian heuristic
Babai's algorithm, cryptosystems based on lattices | #6.16, 6.17, 6.18
Read 2.10.1 - 2.10.3 and try 2.34(b) |
| Nov. 18
Nov. 20 | polynomial rings, convolution
NTRU Encryption | #6.20, 6.21(b), 6.22(c), 6.23, 6.27,6.30, 6. 32
This is due on Thurs. Dec. 4 |
| Nov. 25
| No Class
| Happy Thanksgiving
|
| Dec. 2
Dec. 4 | Security of NTRU, LLL algorithm
Digital signatures, NTRUSign | #6.39, 6.40, 6.41 (optional)
|
| Dec. 9
Dec. 11 | Reading period
Danny's review session is in MetChem 305 noon-2pm. |
Turn in projects Monday Dec. 15 to my mailbox. |