CSE 599B: Cryptography

Cryptography

CSE 599B
Autumn Quarter 2009


Course Info Schedule Homeworks Links

Course Info

Dates/Times: Tues & Fri 10:30-11:50am
Location: CSE 503

Instructor:
 Melissa Chase
Email:
Office Hours: TBD

Course homepage: http://www.cs.washington.edu/599B

Course Overview

How can two people who have never met communicate securely over a network?

How can I sign my messages so that my friends can be certain that they are from me?

What does it mean to say that a cryptosystem is hard to break?

How can we tell if one cryptosystem is more secure than another?

Is it possible to construct an encryption scheme that I can prove cannot be broken?

 This course will be an introduction to cryptography -- the study of techniques and algorithms to allow parties to communicate securely in an untrusted environment. We will focus on algorithms to ensure privacy and authenticity of messages. Topics will include symmetric encryption, stream ciphers/pseudorandom number generators, block ciphers, message-authentication codes (MACs), collision-resistant hash functions, key-exchange, public key encryption, and digital signatures. (We may also touch on more advanced topics such as secure multiparty computation, anonymous credentials, or electronic voting as time permits.)

An underlying goal of this course will be to understand how to rigorously define and evaluate security of cryptographic schemes. With each of the above primitives we will consider a variety of security definitions in order to understand how to clearly define what is meant by security. Then we will see how we can construct schemes which we can prove satisfy these definitions under precisely stated and widely believed assumptions.

What this course will not cover Cryptography is just one aspect of computer security - this course will not teach how to secure your computer against buggy code or denial of service attacks, or how to protect against viruses, worms, etc. We will discuss cryptographic algorithms, but will abstract away many of the implementation details. Finally, this course will not teach how to build your own block cipher. It will, however, discuss how we define and analyze the security of such cryptographic tools, and how to securely combine them in more complex systems.

Textbook

This course will roughly follow Introduction to Modern Cryptography by Katz and Lindell. It is not required, as all necessary info will be covered in lecture. However, I will not be posting slides or lecture notes, so you may find it helpful to have a reference.



Tentative Schedule
10/2 What is cryptography; Historic ciphers; definitions of encryption
10/6 Information Theoretic Encryption/Perfect Security
10/9 Symmetric Key Encryption: Computational Security, Definitions, Indistinguishability, Reductions
10/13 Pseudorandomness: definition of pseudorandom generator (PRG), constructing CPA secure encryption from a PRG
10/16 Pseudo-random functions: definitions, Encryption: modes of operation
10/20 MACS: definitions, fixed length MAC
10/23 Hash functions: definitions, NMAC, HMAC, CCA-secure encryption
10/27 10/28 Definitions of one way functions (OWFs), trapdoor permutations(TDPs), Number Theory: discrete log, Diffie-Hellman
11/3 Key Exchange
11/6 Public Key Encryption: definitions, construction from TDPs, hybrid encryption
11/10 RSA, how not to use it
11/13 El Gamal, CCA security definition
11/17 Signatures: Definitions, RSA, Hash + Sign
11/20 Random Oracle Model: what is it, pros and cons, RSA-FDH
11/24 Random Oracle Model: Encryption
12/1 Advanced Topics
12/4 Advanced topics
12/8 Advanced topics
12/11 Advanced topics


Homeworks

Due
Homework 1 10/16
Homework 2 10/23
Homework 3 10/30
Homework 4 11/13
Homework 5 11/20



Assignments and Grading

Homeworks

Often the best way to understand various security definitions and cryptographic schemes is to work with them, so the course will have problem sets assigned roughly once a week. You are encouraged to collaborate on problem sets. The only requirements are (1) that everyone writes up his/her own solution independently, and (2) that the homework should list all of the students with whom you discussed the problem.

At the end of the semester we will drop the lowest homework grade. Late homework will not be accepted.

Exams

There will be one or two midterms. Essentially these will be problem sets on which collaboration is not allowed.

Final Project

There will be a final project involving further research into a subject of your choice. More information on this later in the quarter.

Grading

Participation 5%
Homeworks 50%
Project 25%
Midterms 20%



Links

Coming soon.