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/fall2014/
Office Hours: M 11:00-12:00 (Room 632)
TA: Mark Mullock
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 Mark <mmullock@u.rochester.edu>
There will be roughly 4-5 homeworks and 2 exams. Students taking the graduate course will be expected to do a final project. The grade will be based on homework assignments, exams and class participation.
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 (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.
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.
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:
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms.
Michael Sipser. Introduction to the Theory of Computation.
9/2 Lecture 1: What Crypt can do for you? the match-making game and zero-knowledge
9/9 Lecture 2: Basics of Number Theory and Number Theoretic Algorithms
9/16 Lecture 3: Kerchoff's principle, Historical Ciphers (Chapter 1 from Pass-shelat Notes)
9/18 Lecture 4: Shannon's definition of secrecy and One-Time Pad (Chapter 1 from Pass-Shelat Notes)
9/19 Lecture 5: One-way functions (OWF), Worst-Case and Strong OWF(Chapter 2 from Pass-shelat Notes)
9/23 Lecture 6: Weak OWF based on the Factoring Assumption (Chapter 2 – 2.3)
9/25 Lecture 7: Strong OWF based on the Factoring Assumption (Chapter 2 – 2.4.2)
9/30 Lecture 8: Basics of Computational Number Theory (Chapter 2 – 2.6.4,2.6.5)
10/2 Lecture 9: OWF based on the Discrete Logarithm Assumption(Chapter 2 – 2.8)
10/7 Lecture 10: OWF based on the RSA Assumption(Chapter 2 – 2.9)
10/9 Lecture 11: Computational Indistinguishability, Properties of Indistinguishability – Closure under Efficient Operations / Transitivity (Chapter 3 – 3.1, 3.1.1)
10/14 Lecture 12: Pseudorandom Generators (PRG), 1-bit to poly-bit expansion of PRGs (Chapter 3 – 3.3,3.3.1,3.3.5)
10/16 Lecture 13: Hard-Core predicates, PRGs from OWFs and Hard-Core predicates (Chapter 3 – 3.3.3,3.3.4)
10/21 Lecture 14: Hard-core predicate for the Discrete Logarithm OWF (Chapter 3 – 3.4.1)
10/23 Lecture 15: Single-message semantic-security, Multi-message semantic-security, Random Functions (Chapter 3 – 3.6,3.7,3.8)
10/25 Lecture 16: Pseudorandom Functions (PRF) and Multi-message semantic-secure encryption scheme (Chapter 3)
10/28 Lecture 17: Multi-message secure encryption scheme using Random Functions and Functional/Oracle-Indistinguishability
10/30 Mid-Term
11/4 Lecture 18: Multi-message secure encryption from PRFs and Public-Key Encryption.
11/6 Lecture 19: RSA and El-Gamal encryption scheme
11/11 Lecture 20: Block ciphers and Stream ciphers
11/13 Lecture 21: MACs and Digital Signatures
11/18 Lecture 22: Collision-resistant Hash Functions and Bitcoins
11/20 Lecture 23: Key Management and Public-Key Infrastructure Transfer
11/21 Lecture 24/25: Extra Class: 6:00p-9:00p Zero-Knowledge, Oblivious Transfer and Secure Computation
11/25 Lecture 26: Stronger/Alternate notions of Encryption: Zero-Knowledge, CPA/CCA1/CCA2
11/27 Thanksgiving
12/2 Lecture 27: Network Security I
12/4 Lecture 28: Network Security II
12/9 Lecture 29:
12/11 Lecture 30:
9/23 Adam Scrivener – Enigma and World War II
9/25 Amelia Norvell – SQL Inject Attack
11/6 Cameron Caswell – Attacks on Encryption Schemes
11/11 Eric Podsaidly – TOR
11/13 Invited Speaker
11/18 Justin Fraumeni
11/20 Priya Thomas
11/25 Annie Zhang
12/2 Grace Heard
12/4 Eric Campbell
MTH 233: Introduction to Cryptography