Introduction to Cryptography

University of Rochester

Spring 2021

Instructor: Muthu Venkitasubramaniam

Time: TR 2:00-3:15

Place: Virtual (Check blackboard for zoom link)

Course Web page: http://www.cs.rochester.edu/courses/281/spring2021/

Office Hours: By appointment

TA: Laasya Bangalore (lbangalo@ur.rochester.edu), Office Hours: TBD

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 will introduce some of the fundamental concepts,
protocols with rigorous proofs of security.

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 Blackboard for this course.

Grading

Homeworks (30%) - There will be 5-6 homeworks.

Quizzes (30%) - There will be a quiz every class.

Midterm (30%) - There will be two midterms. (Midterm 1: 3/18, Tentative date for Midterm 2: 4/20)

Project (10%)

Homework Policy

You are free to collaborate with a maximum of two other students on the homework, but you
must turn in your own individually written solution and you **must specify** the names of your collaborators. You are allowed
refer online material but you are not allowed to solicit solutions online.
You must specify any and all online material that you referred.
On midterms, you are not allowed to collaborate with other students and you are not allowed to refer any material beyond
the resources specified on this webpage. Note that it is a violation of this
policy to submit a problem solution that you are unable to explain orally to
me. All homeworks and midterms have to be typeset.

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.

· **[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.

2/2 Lecture 1: What can cryptography do for you? the match-making game and Kerchoff’s principles (**[PS]** 1.1, 1.2 )

2/4 Lecture 2: Historical Ciphers, Introduction to Modern Cryptography (**[PS]** 1.1, 1.2 )

2/9 Lecture 3: Basics of Probability (Pass's Discrete Structures course: Chapter 5 )

2/11 Lecture 4: Shannon secrecy, Perfect secrecy (** [PS] ** 1.3,1.4)

2/16 Lecture 5: Limit of Shannon secrecy, Basics of Computability (** [PS] ** 1.3,2.1)

MTH 233: Introduction to Cryptography