Introduction to Cryptography

University of Rochester

Fall 2012

Instructor: Muthu Venkitasubramaniam

Time: TR 12:30-13:45

Place: CSB 632

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

Office Hours: TBD

TA: Scott Ames

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.

Note: This will be a theory course. You will be expected to read and write formal definitions and mathematical proofs. This is not a course in security: you will not learn how to secure your system. Cryptography is only one (important) part of security. We will not study cryptographic acronyms or all cryptographic protocols in use today. Rather we focus on some of the fundamental design paradigms and on notions that will allow you to critically evaluate cryptographic protocols.

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

Course Administration

TBD

Grading

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 (and the final project).

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 (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.

TBD

MTH 233: Introduction to Cryptography