Introduction to Cryptography

Computer Science 281/481
University of Rochester
Fall 2015



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)

Overview

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.  

Prerequisites

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.


Course Administration

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)


Grading

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%

Workshop

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


Homework Policy

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.


Reading

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.

For a more applied treatment of cryptography, I suggest the following book which is available on-line.

For background reading on probability, algorithms, and complexity theory, I recommend:

 

Lectures Outline

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])

Presentation Schedule

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”





Related Course

MTH 233: Introduction to Cryptography