Course Description:
Cryptography is the study of the design and analysis of various encryption schemes, and related topics. The plan is to study the basics of the subject and then touch on several recent developments. Although cryptography has been used for centuries, the subject changed significantly in the 1970s with the development of public-key cyptography and the RSA algorithm, which is fundamental for today's internet security. At this point, cryptography became much more mathematical, particularly number theoretical. Many more new ideas were subsequently introduced (elliptic curves, zero-knowledge proofs, secret sharing schemes, and improved hash functions, proofs of security, for example). We'll cover all these topics, plus, as time permits, very recent developments such as pairing-based cryptography (including ID-based encryption) and homormorphic encryption. This course will not teach you how to steal passwords or how to design firewalls. Instead, it will examine the basic ideas that lie behind the cryptographic algorithms that are in use today. The basic prerequisite is mathematical maturity (at the level of someone who has done well in two 400-level courses). It will also be assumed that students are familiar with modular arithmetic, basic matrix operations, and a computer language such as MATLAB or Mathematica. The necessary number theory (for example, Euler's theorem and the Chinese Remainder Theorem) will be covered during the course.
Grading: Homework 15%, Two midterms: 25% each, Final: 35%
The midterms are tentatively scheduled for Thursday, Otober 3, and Thursday, November 21. The final exam will be on Saturday, December 14, 10:30am-12:30pm.
Homework is due by 10:59:59pm on the due date (the math building closes at 11pm). Late homework will be accepted; however, the score will be reduced by a factor of 50%.
Approximate syllabus: (subject to adjustment):
1. Construction and analysis of simple cryptosystems (shift, affine, Vigenere, linear feedback shift registers)
2. The one-time pad and perfect secrecy
3. Public key cryptography (RSA, finding large primes, factoring techniques, ElGamal systems)
4. The Data Encryption Standard and the Advanced Encryption Standard
5. Signature schemes (how to sign an electronic message)
6. Electronic currencies
7. Secret sharing schemes (design a system that can be activated by any 5 people in a group, but never by 4)
8. Hash functions
9. Zero-knowledge proofs (prove that you have some information without revealing the information)
10. Elliptic curves and ID-based cryptography
