CS181A Cryptography

Spring 2012

Syllabus

Cryptography is a study of secure communication over insecure channels. The first half of this course is devoted to basic concepts in modern public-key cryptography along with their applications. Topics covered include (but not limited to) one-way functions, pseudorandom generators, probabilistic encryptions, digital signatures, cryptographic hash functions, and zero-knowledge proofs. Relevant background from number theory, probability theory, and complexity theory will be developed together with the main topics. The second part of the course examines the recent impact of quantum physics on cryptography. Specific topics covered include Shor's factoring algorithm and quantum key distribution protocols. No prior background on quantum physics is required.

Lecture:

TR 09:35-10:50, Parsons B144

Instructor:

Christino Tamon (Olin 1241, x-70443). Office hours: MW 10-11am, TR 2-3pm

Grading

Assignments (40%). Quizzes (30%). Final project (30%).

References

There are no official textbooks but a good reference for the first part is D. Stinson, Cryptography: Theory and Practice, 3rd edition, Chapman and Hall/CRC, 2006, and a good source for the second part is M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.

Responsibilities

Attendance

Not mandatory but you are resposible for any material or activities covered in class.

Announcements

Any course announcements will be given in class or via the course mailing list. You are responsible to read the course mailing list.

Late Policy

You have five late days that can be used to extend homework assignments across the semester. No other extensions will be allowed unless requested by the dean.

Collaboration

You are encouraged to discuss any course material with your fellow students but any submitted work must ultimately be your own. Any help you received on your submitted work must be acknowledged. You should come away from any discussion with your fellow students with a real understanding (and not a documented softcopy or hardcopy solution provided by someone else). Any discussion you have on the homeworks should take place on an equal basis (neither receiving complete answers nor giving away complete answers).

Project

Objective

The project is an opportunity to explore topics in cryptography that is of interest to you. Some topics for the project will be suggested by the instructor but you may also work on a topic of your own choosing (with consultation with the instructor). As part of your project, you should prepare a final report (at least 10 pages in length) and present a final talk (for a 20-30 minute talk). You may choose to work alone or in pairs.

Report

Your final report should include a clear description of the cryptographic area and the relevant interesting problems, a literature review of this area, a discussion of what are known (main results of the area), and a description of the main open problems in the area. As part of the project, you should plan to read in detail one or two research articles that are relevant and of interest to you. Your report should include a careful exposition of the research articles you read and a set of (at least two) questions which you feel were not addressed by the paper(s) and might be interesting to you for future research. You should attempt to solve one of this suggested open problems to the best of your abilities and a report of your efforts should be included in the report.

The final report should be prepared with TeX and submitted as a PDF file by email (and includes any accompanying programs or implementations relevant to the project). The length of this report should be around 10 pages (including bibliography and figures).

Presentation

Your final talk should include some of the components of your report (problem description, relevance to cryptography, main results in the area, open problems, and your personal efforts to address one of the main open problems you had identified).

The slides of the talk should be prepared using TeX/Beamer (or similar tools) and should be submitted as a PDF file by email. Your talk will be presented to the class and should be 20-30 minutes (including questions).

Possible Topics

Course Schedule:

Week Date Topic HWs Notes
1 Jan 17,19 Secret- vs public-key cryptography [Do] HW1 notes-1
2 Jan 24,26 Basic number theory [A82] HW2 notes-2
3 Jan 31, Feb 2 RSA and its details [RSA78] HW3 notes-3
4 Feb 7,9 ElGamal and Diffie-Hellman [DH76] HW4, keys notes-4
5 Feb 14,16 Elliptic Curves [KKM] [GK99] HW5, keys notes-5
6 Feb 21,23 Quadratic Residuosity [GM84]   notes-6
7 Feb 28, Mar 1 Zero-knowledge proofs [Ba] [GMR89]   notes-7
8 Mar 6,8 Protocols HW6, keys  
9 Mar 13,15 Spring break    
10 Mar 20,22 AES and DES: [L]   notes-8
11 Mar 27,29 Basic quantum information: [Gu], [Mer]    
12 Apr 3,5 Quantum key distribution   notes-9
13 Apr 10,12 Quantum algorithms: Zoo    
14 Apr 17,19 Shor's algorithm   notes-10
15 Apr 24,26 Further topics   notes-11
16 May 1,3 No classes   notes-12
17 May 8,10 Finals week