Course Outline

This course serves as the introduction to cryptography for advanced undergraduates and graduate students. The focus is on definitions, theoretical foundations, and rigorous proofs of security. This course is cross-listed with the mathematics department, so it will have a significant mathematical component. This course complements Computer and Network Security (CMSC 414) which focuses more on "high-level" issues; in this class, we will actually look "under the hood" and attempt to understand various cryptographic protocols and algorithms. This course and CMSC 414 may be taken in either order.

We will begin with a brief discussion of "classical" cryptography and its limitations. Following this, we will define a notion of "perfect" security and see what can and cannot be achieved in this sense. This will lead us naturally to the modern, complexity-theoretic approach to cryptography in which security is based on the assumed computational hardness of various problems. In this vein, we will study pseudo-randomness, private-key (i.e., shared key) encryption and message authentication, block ciphers, authentication, public-key encryption, and digital signatures. Advanced topics will be covered as time permits.

No advanced mathematics background is assumed, but students are expected to possess "mathematical maturity" since many of the concepts will be abstract and rigorous proofs will be given occasionally throughout the semester. Discrete mathematics (probability theory, modular arithmetic) and complexity theory are also helpful, but the necessary prerequisites will be discussed in class.

The textbook for the course is "Cryptography: Theory and Practice, 2nd edition" by Stinson. The second edition is very different from the first edition; please do not use the older version of the book. Additional readings will be listed on the course homepage.

Important Information Regarding the Final Exam

The final exam for CMSC 456 is scheduled by the University to be on Thursday December 18th from 10:30-12:30. However, due to a work-related conflict of the professor, it is requested that the final exam be on Thursday December 11th, either from 2-4 PM (the regularly scheduled class is from 2-3:15pm) or else from 6-8 PM. It is requested that students confirm, via an email to the professor, whether or not they have any objections to this; additionally, if there are questions/concerns, they may be sent to the professor and/or also be addressed to the Undergraduate Program Coordinator (James Maybury, jmaybury@cs.umd.edu). Note added on Oct 2, 2003: The final exam times are confirmed now, to be on Dec 11th and Dec 12th; please see announcement a few lines below. Note added on Oct 19, 2003: The final exam times and venues are confirmed now, to be on Dec 11th and Dec 12th; please see announcement dated Oct 19, a few lines below.

Announcements

• [Posted 9/23/2003]: The mid-term exam will be held in class 2-3:15 PM on Tuesday, October 28, 2003. It will include all material covered up to and including the class of October 21.
  
  
• [Posted 10/01/2003]: The mid-term will be closed-book, closed-notes. However, you can bring one 8.5 x 11 sheet with anything written on it. As announced before, the mid-term will be in class on Tue, 10/28. The material included is as follows: (a) all material covered up to and including the class of Oct. 21; and (b) anything that you were asked to read as part of the homework assignments.
  
  
• [Posted 10/01/2003]: The time-slots for the final are confirmed now. They will be offered on Thu, Dec. 11 at: (i) 2-4 PM, (ii) 6-8 PM, and (iii) 7-9 PM. You can choose any of these slots. (Also, one of you will take it on Fri, Dec 12, 9-11 AM.) The exams will be sufficiently different, but you will also be asked to not discuss them with anyone for a day after you take the exam. I will announce the venues soon after they are confirmed.
  
  
• [Posted 10/01/2003]: A link to errors in the book has been added below. I thank Walid Gomaa, Richard Gopaul, and Christine Smit for pointing out the errors in the description of the Euclidean Algorithm.
  
  
• [Posted 10/19/2003]: The venues and time-slots for the final are confirmed now. The exam will be offered on Thu, Dec. 11 at: (i) 2-4 PM in Room 0119 of the Armory, (ii) 6-8 PM in CSI 2117, and (iii) 7-9 PM in CSI 2117. You can choose any of these slots. (Also, one of you will take it on Fri, Dec 12, 9-11 AM, in my office, A.V.Williams 3227.)
  
  
• [Posted 11/06/2003]: Aravind's office hours today are canceled. Please email him some possible time-slots for you in the next few days, if you had planned on coming to the office hours today.
  
  
• [Posted 11/12/2003]: Problem 1 in HW 5 has now been corrected: the number of repetitions is k^3, instead of (ln k)^3. My apologies for this error --Aravind.
  
  
• [Posted 11/17/2003]: Due to the requests of some of you, the deadline for submission of HW6 has been postponed to the beginning of class on Tuesday, Nov 25.
  
  
• [Posted 11/18/2003]: Walid Gomaa has pointed out that the repeated-squaring pseudocode presented in class is incorrect, and has provided this corrected version. Thanks to Walid for this.
  
  
• [Posted 12/01/2003]: As pointed out by Sun Kim, there is a typo in HW 7. In problem 2, what we want is an x such that f(x) = y; this has been fixed now. Thanks to Sun for this.
  
  
• [Posted 12/08/2003]: The final exam will be closed-book, closed-notes. However, you can bring one 8.5 x 11 sheet with anything written on it. The material included is as follows: (a) all material covered in class; and (b) anything that you were asked to read as part of the homework assignments.
  
  
• [Posted 12/08/2003]: Jonathan Katz's midterm and final from Fall 2002 are posted below.
  
  
• [Posted 12/09/2003]: The review session by Charles Clancy will be in CSI 1121 at 7PM on Wednesday, Dec. 10.

  General Information

  • Grading will be based on 6-7 homeworks assigned throughout the course (40%), a midterm (25%), and a final exam (35%).
  • Graduate students taking the course (both Masters and PhD students) will be required to do additional problems for homework. Their grades will also be curved independently of those of the undergraduate students.
  • Homework:
    • You may collaborate on the homeworks with at most one other student in the class. Each student must independently write up their own solutions, and include the name of their collaborator, if any.
    • You may consult outside references when doing the homework, as long as these sources are properly referenced, you write up the solution yourself, and you understand the answer.
  • Course Philosophy: The more interactive the class is, the better it will be for all of us: we can get better insights into the material, and enjoy the process better. Students are strongly encouraged to participate actively in class. All of us hesitate occasionally in asking questions; the instructor will do his very best to encourage questions. Doing the homework to the best of your ability, comparing your solutions to the handed-out ones, and seeing if you can do better, is the best way of understanding the course material.
  • Check the course homepage frequently since all handouts will be distributed via the web and an updated syllabus will be maintained on this page.

  Staff

  Professor:	Aravind Srinivasan (srin AT cs) Office: 3227 A.V. Williams Building, Phone 405-2695. Office hours: Tuesday, Thursday 1-2 PM.
  Teaching Asst:	T. Charles Clancy (clancy AT cs) Office hours: Monday, Wednesday 11AM - 12 noon, held in room 1112, A.V. Williams Building.

  ---

  Course Material

  • Suggested Readings (mostly the same as in Jonathan Katz's 456 class from Fall 2002)
    
    
  • Lecture Schedule
    
    
  • Book Errata
    
    
  • Fall 2002 Mid-Term
    
    
  • Fall 2002 Mid-Term Solutions
    
    
  • Fall 2002 Final
    
    
  • Handouts

    Posted	Document	Download		Description
    8 September	Algebra & Number Theory Notes	PS	PDF	Notes from the Fall 2002 course.
    8 September	Discrete Probability Notes	PS	PDF	Notes from the Fall 2002 course.

  • Assignments

    Posted	Document	Assignment		Solution		Due	Ugrad Avg/Max	Grad Avg/Max
    8 September	Homework 1	PS	PDF	PS	PDF	23 September	16.5 / 23	29.5 / 33
    23 September	Homework 2	PS	PDF	PS	PDF	2 October	14.8 / 18	23.5 / 30
    5 October	Homework 3	PS	PDF	PS	PDF	14 October	13.6 / 20	25.3 / 28
    14 October	Homework 4	PS	PDF	PS	PDF	23 October	13.0 / 18	22.3 / 28
    28 October	Exam 1	PS	PDF	PS	PDF	28 October	18.9 / 25	31.7 / 35
    4 November	Homework 5	PS	PDF	PS	PDF	13 November	15.5 / 20	19.3 / 25
    13 November	Homework 6	PS	PDF	PS	PDF	25 November	9.1 / 10	15 / 15
    26 November	Homework 7	PS	PDF	PS	PDF	9 December	12.5 / 15	18.7 / 23

    Average scores do not reflect extra credit, which will only be considered at the end of the semester.