**PENN CIS 620, FALL 2007: FOUNDATIONS OF CRYPTOGRAPHY
**

Prof Michael Kearns

mkearns@cis.upenn.edu

Mondays
12-3 PM

315 Levine Hall

URL for this page:
www.cis.upenn.edu/~mkearns/Crypto

**SEMINAR DESCRIPTION**

In this seminar we will undertake a detailed study of the mathematical foundations of modern, complexity-based cryptography, as well as its connections with other topics in theoretical computer science, including computational learning theory, algorithmic game theory, and privacy-preserving data mining and inference. The emphasis of the seminar will be on the conceptual rather than the practical. As opposed to an "applied" cryptography or security seminar, we will be primarily interested in the broad possibilities for, and limits on, secure computation.

The first part of the seminar will be more structured and will closely follow Oded Goldreich's superb Foundations of Cryptography, Volume I (Basic Tools). Topics to be covered include:

The latter portion of the seminar will examine connections between the fundamental cryptography topics above and other branches of theoretical computer science, including:

The required seminar text is Oded Goldreich's book Foundations of Cryptography, Volume I (Basic Tools) which is on order at the bookstore. Depending on our rate of progress, it is possible we will also use Goldreich's Volume II, though I am not requiring it yet. We will also examine papers from the cryptography literature which I will post directly on this page (see Additional Readings below).

Please note that there is a complementary course on computer and network security being offered this term by Prof. Andre Scedrov in the math department.

**SEMINAR FORMAT, REQUIREMENTS, AND PREREQUISITES **

The first portion of the seminar (based on Goldreich's book(s)) will be in what we might call "semi-" or "assisted" lecture format. I will structure the broad discussion and lecture a bit, but each week there will be one or more designated discussants whose role is to help present proofs or proof sketches/intutions, present additional material such as solutions to exercises in Goldreich, etc. Participants taking the seminar for credit will be expected to act as discussants.

The latter portion of the seminar, when we are examining applications of cryptographic tools to other areas such as computational learning theory, will be run in reading-group format, with different participants leading informal discussion of papers.

In order to allow plenty of time for leisurely discussion, the seminar will meet once a week on Mondays from 12 to 3. Lunch will be served.

Participants should be comfortable with the basics of computational complexity, design and analysis of algorithms, and probability theory. Some exposure to number theory will be helpful at certain points but is not required.

Auditors and occasional participants are welcome. Strong undergraduates are also encouraged to join.

READING: Goldreich Chapter 2.

Mon Sep 24

We will finish our study of Goldreich Chapter 2 and continue straight on into
Chapter 3; this week's assistant is Jinsong Tan.

Main topics:

READING: Goldreich Chapter 3.

Also, check out this talk of directly related interest by Jenn Wortman on Weds Sep 26.

Mon Oct 1

We will finish up our study of Chapter 3 on pseudorandomness, and trundle on into
Chapter 4, interactive and zero-knowledge proofs. This week's assistant is Kuzman Ganchev.

READING: Goldreich Chapter 4.

Mon Oct 8

We will continue our study of zero-knowledge with Kuzman, and Andrew Clausen
will present some of his own work on composing zero-knowledge proofs; here is
a related
handout.

READING: Goldreich Chapter 4 continued, and the handout.

Mon Oct 15: FALL BREAK, NO MEETING

Mon Oct 22

We move on this week to study secure multiparty function computation (SMFC); for this
we will use
Oded Goldreich's notes on the topic.
We'll mainly stay in the first two chapters, but please skim the third as well. Jenn Wortman
will be this week's assistant.

READING: Goldreich SMFC notes.

Mon Oct 29

We now morph into "application" mode, where we will study the interaction of
cryptography with various other topics in theoretical computer science. We will
begin with computational learning theory, which will probably cover two sessions.
For starters, let's look at the papers below; Alex Kulesza will assist.

Mon Nov 5

Computational learning theory and cryptography, continued.

Mon Nov 12

This week we will examine research at the intersection of game theory and
cryptography, assisted by Jinsong, Jenn, and Andrew.

Mon Nov 19

This week will examine the logic-based approaches to security and how
they relate to the computational view, with Jeff Vaughan
assisting.

Mon Nov 26

For our final meeting, we will cover papers on privacy-preserving data mining
and code obfuscation, assisted by Mark Dredze. We'll use the remaining time
to hear Andrew Clausen discuss some of his own research.

Mon Dec 3

NO MEETING. I am proud to announce that this is probably the first
cryptography seminar ever to be cancelled due to NIPS:). Enjoy your holidays
and thanks for a great semester --- I learned a lot.

**ADDITIONAL READINGS**

Here I will collect papers from the literature that may eventually migrate onto our meeting schedule.

**Cryptography and Computational Learning Theory**

**Cryptography and Algorithmic Game Theory**

**Privacy-Preserving Data Mining and Inference**