Professor: Jeff Hoffstein
Office: 104 Kassar-Gould House
Email: jhoff@math.brown.edu
Office Hours: 1-3 Monday, or by appointment
ALERT!! CHANGE OF TIME AND LOCATION!!: There will be an optional 1 hour problem solving session on Monday evenings from 7-8 in BH 163.
Grades in the course are based on
weekly homework assignments (25%), one midterm (25%)), one
project (15%)
and the final examination
(35%).
Homework assignments and due dates will be posted
on the website. I will discuss my policy about students
working together on homeworks in class.
There will be an (optional) problem solving session on Monday evenings, time to be determined.
Plan on taking the final exam at the scheduled time. I only
give make-up exams for illness or conflicts with other scheduled exams.
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.
This website will be updated weekly. The schedule below, in particular should be viewed as EXTREMELY tentative.
THE PROJECT: There are an incredible number of interesting ideas that I won't
have a chance to cover this semester. I'd like you to compensate for this
just a little bit by choosing an area of cryptography that interests you
and exploring it. This can mean taking something we've done and going
further, or looking at something completely new. For example, possible
topics include elliptic curve cryptography (including, if you like, the
elliptic curve factoring approach), further analysis of other factoring
algorithms, such as the quadratic sieve or the number field sieve, index
calculus and discrete logarithms, quantum computing, quantum cryptography,
digital cash, internet voting, signature schemes that we don't get a chance
to talk about, and those that we do taken further, threshold secret
sharing,...., aspects of lattice based cryptography that go beyond what
we discuss, such as Atjai-Dwork, GGH, knapsack problems and NP hard
problems, and the list goes on.
List of errata and other things: http://www.math.brown.edu/~jhs/MathCryptoHome.html
THE FINAL EXAM IS Friday December 16 from 2-5
| Calendar | Material Covered | Homework Assignments |
Sept 10 | Overview | See below for HW #1 |
| Sept 15
Sept 17 | The Euclidean algorithm and modular arithmetic
Modular arithmetic and finite fields | |
| Sept 22 Sept 24 | Fermat's Little theorem, primitive roots. fast exponentiation
symmetric ciphers, discrete logarithms | 1.17 a-e ; 1.18; 1.22; 1.25,a;c1.30,a;1.31; 1.32,a |
| Sept 29 Oct 1 | Diffie-Hellman, El Gamal | 1.41,1.42, 1.48, 2.4, 2.5, 2.6, 2.8, 2.10 |
Oct 6 Oct 8
| Chinese remainder theorem, square roots mod n No Class (Will be made up during reading period. Problem session in place of class - same time, same place.) | 2.16 a,b,f; 2.18 a,d; 2.19; 2.23 a,c; 2.26; 2.27 Due Oct 13 |
| Oct 13 Oct 15 | Pohlig- Hellman, Euler's theorem RSA and some simple attacks |
2.28 a (you can do it!); 3.1 a,c; 3.2;3.6,3.7, 3.8 a; 3.12; Due Oct 22 |
Oct 20 Oct 22 | Attacks on RSA, primality testing Miller-Rabin test, distribution of primes, Pollard's p-1 factorization method | |
Oct 27 Oct 29 | Midterm (in class) Return of midterm (I hope!), Quadratic reciprocity, Goldwasser-Micali cryptosystem | |
Nov 3
Nov 5 | The N=1 case of NTRU, subset sum problems
Introduction to lattices
| 3.14 b,d; 3.15; 3.21 b; 3.41 a; Due Nov 10 Read sections 6.1,6.2
|
Nov 10 Nov 12 | Lattices, Gaussian heuristic, short vectors | 6.1; 6.3; 6.9*; 6.13 (The * means that 6.9 is optional and extra) |
Nov 17 Nov 19 | Short vectors, closest vectors, Babai's algorithm, the GGH cryptosystem | 6.17; 6.18 Due Nov 24 |
Nov 24 Nov 26 | Polynomial rings and NTRU Thanksgiving! | 6.50 a; Read 2.10. |
HW #1: Read Chapter 1. Problems: 1.5a (Try b and see what you can do...); 1.6; 1.7c,d; 1.9a,d; 1.10 a, d; 1.11