Introduction to Cryptography
Instructor: Muthu Venkitasubramaniam
Time: TR 12:30-13:45
Place: CSB 632
Course Web
page: http://www.cs.rochester.edu/courses/281/fall2015/
Office Hours: (Muthu) By appointment
(Adam) TBD
TA: Adam Scrivener (ascriven@u.rochester.edu)
TA: Jacob Bisnett (jbisnett@u.rochester.edu)
Modern cryptography studies techniques for facilitating interactions between distrustful entities. Today, with the advent of the Internet, these techniques become indispensable – enabling, for instance, anonymous electronic elections, privacy-preserving electronic auctions, internet banking and more. In this course we introduce some of the fundamental concepts of this study.
Topics Include: one-way functions, private-key/public-key encryption systems, digital signatures, zero-knowledge, secure-multiparty computation and its applications.
CS 280 (or equivalent), MTH150 (or mathematical maturity), or
permission of instructor.
The main skills that will be assumed
from these courses are: 1) the ability to understand and write formal
mathematical definitions and proofs and 2) comfort with reasoning
about algorithms, such as proving their correctness and analyzing
their running times. It is also important that you are familiar with
basic probability.
We will be using Piazza for this course. If you have not been invited please send an email to Adam Scrivener (ascriven@u.rochester.edu)
There will be 4-5 homeworks and 2 exams. Students taking the graduate course will be expected to do a final project. Every student will have to make a presentation on a security related topic. There will be workshops that are mandatory where the TA will engage and assist in solving problems. The grading scheme will be:
Homeworks 40%
Presentation 10%
Workshop 20%
Midterm or Final 20%
Quiz 10%
You will be assigned to workshops. Please attend the workshop you have been assigned to.
Workshop 1: Tuesday 4:00-5:15 (CSB 632) – Adam Scrivener
Workshop 2: Wednesday 4:50-6:05 (Hylan 101) – Jacob Bisnett
Workshop 3: Friday 4:00-5:15 (CSB 601) – Adam Scrivener
You are free to collaborate with other students on the homework, but you must turn in your own individually written solution and you must specify the names of your collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used. Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to me. Typed problem sets are strongly preferred.
Lecture notes covering a large fraction of the course can be found here [PS] (course notes developed by Rafael Pass and abhi shelat).
There is no required text for the course other than lecture notes. You may find the following two books to be useful references. Note, however, that we will not always be following the same notational conventions as these books.
[KL] Jonathan Katz and Yehuda Lindell. An Introduction to Modern Cryptography. This is an introductory textbook on cryptography. The level of the material and the mathematical treatment is similar to the one we will use in class. However, this book does not cover all of the material that we go through.
[G] Oded Goldreich. Foundations of Cryptography. This is a very comprehensive treatment of the theoretical foundations of cryptography. Volume I and II include most of the material that we cover in class, but at a far greater depth and (at a more advanced level). This book is a great reference for students interested in more advanced studies in theoretical cryptography.
For a more applied treatment of cryptography, I suggest the following book which is available on-line.
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography.
For background reading on probability, algorithms, and complexity theory, I recommend:
[CLR] Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms.
Michael Sipser. Introduction to the Theory of Computation.
9/1 Lecture 1: What Cryptography can do for you? the match-making game and zero-knowledge
9/3 Lecture 2: Kerchoff's principle, Historical Ciphers (Chapter 1.1 from [PS])
9/8 Lecture 3: Introduction to Probability (Link to László Babai's notes)
9/10 Lecture 4: Shannon secrecy, Perfect Secrecy. Shannon's one-time pad. (Chapter 1.3 from [PS])
9/15 Lecture 5: Introduction to Number Theory I-Modular Arithmetic, Extended-Euclid Algorithm, Additive and Multiplicative Groups modulo p, Euler's Totient Function (Chapter 2.6 from [PS])
9/17 Lecture 6: Introduction to Numbert Theory II-Additive and Multiplicative Groups modulo N. Basics of Computability theory: Algorithms, Turing Machines, Randomized Algorithms, Probability Polynomial Time, Efficient Adversaries (Chapters 2.1 and 2.6 from [PS])
9/22 Lecture 7: One-way Functions, Noticeable and Negligible functions (Chapter 2.2 and 2.3 from [PS])
9/24 Lecture 8: Strong One-Way Functions, Factoring Assumption (Chapter 2.3 from [PS])
9/29 Lecture 9: Constructing Weak One-Way Function from Factoring Assumption (Chapter 2.3 from [PS])
10/1 Lecture 10: Strong One-Way Functions from Factoring Assumption and Miller Rabin Primality Testing (Chapter 2.4 from [PS])
10/6 Lecture 11: One-Way Function from the Discrete Logarithm Assumption (Chapter 2.8 from [PS])
10/8 Lecture 12: One-Way Permutation from the RSA Assumption and Introduction to Pseudorandomness (Chapter 2.9 from [PS])
10/15 Lecture 13: Computational Indistinguishability, Prediction/Indentifying, Semantically-Secure Encryption and Pseudorandom Generators (Chapter 3.1,3.2,3.3 from [PS])
10/20 Lecture 14: Hybrid arguments (Chapter 3.1 from [PS])
10/22 Lecture 15: Constructing Pseudorandom Generators (PRG) from One-Way Permutations and Hardcore Predicates (Chapter 3.4 from [PS])
10/27 Lecture 16: Semantically-secure Encryption Scheme – Definition and Construction based on PRGs (Chaper 3.5 from [PS])
10/29 Lecture 17: Simple Security Reductions for One-Way Functions (Chapter 2.2 from [PS])
11/3 Lecture 18: Pseudorandom Functions (PRFs) and Multi-message Secure Encryption. (Chapter 3.7,3.8 from [PS])
11/5 Lecture 19: Oracle Indistinguishability and PRFs from PRGs. (Chapter 3.8 from [PS])
11/10 Lecture 20: Multi-message Secure Encryption based on Pseudo-random Functions (Chapter 3.9 from [PS])
11/12 Lecture 21: Public-key encryption schemes based on DDH and Trapdoor Permutations (Chapter 3.10,3.11 from [PS])
10/22 Hassler Thurston : Shellshock
10/27 Kezhen Chen: Poodle Attack
10/29 Dong Chen: SQL Injection Attack
11/03 Thomas L V: Netflix Prvacy Contest
11/05 Jiaming Su: iOS XATA
11/10 Joseph Linden: DeCSS – The DVD Encryption Descrambler
11/12 Herbert Bolimovsky: The Equation Group
11/17 Hak Kyung Lee: SSH keystroke Attack
11/19 Tianqin Zhao: Worm virus “Panda joss-stick”
MTH 233: Introduction to Cryptography