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:

  • One-way and trapdoor functions
  • Hardness amplification and hard-core predicates
  • Pseudorandom generation
  • Zero-knowledge and interactive proofs
  • Encryption and digital signatures
  • Secure multiparty computation

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

  • Cryptography and computational learning theory
  • Cryptography and algorithmic game theory
  • Privacy-preserving data mining and inference

    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.

    DETAILED MEETING SCHEDULE

    Mon Sep 10
    In the first meeting, I will go over course mechanics and present a detailed overview of the topics to be covered.

    READING: Goldreich Chapter 1.

    Mon Sep 17 ==> Wed Sep 19: Due to a longstanding commitment I have in D.C., this week's meeting will be held Wed Sep 19 from 12 to 3 PM.
    This week's assistant is Praveen Srinivasan. Topics to be covered this week:

  • definitions of one-way functions
  • weak one-way = strong one-way
  • hard-core predicates

    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:

  • hard-core predicates
  • pseudorandom bit generation
  • pseudorandom function generation

    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.

  • Cryptographic Limitations on Learning Boolean Formulae and Finite Automata. Kearns and Valiant.
  • Cryptographic Hardness of Distribution-specific Learning. Kharitonov.
  • When Won't Membership Queries Help? Angluin and Kharitonov.

    • Mon Nov 5
    Computational learning theory and cryptography, continued.

  • Cryptographic Hardness Results for Learning Intersections of Halfspaces. Klivans, Sherstov.
  • Boosting and Hard-Core Sets. Klivans, Servedio.
  • Separating Distribution-Free and Mistake-Bound Learning Models Over the Boolean Domain. Blum.
  • Cryptographic Primitives from Hard Learning Problems. Blum, Furst, Kearns, Lipton.
  • Evaluation May Be Easier Than Generation. Naor.

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

  • Crytpography and Game Theory. Dodis and Rabin.
  • A Cryptographic Solution to a Game-Theoretic Problem. Dodis, Halevi, Rabin.
  • Transparent Computation and Correlated Equilibrium. Izmalkov, Micali, Lepinski, Shelat.
  • Rational Secure Computation and Ideal Mechanism Design. Izmalkov, Micali, Lepinski.
  • Perfect Implementation of Normal-Form Mechanisms. Izmalkov, Micali, Lepinski.

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

  • Reconciling Two Views of Cryptography. Abadi and Rogaway.
  • A Composable Cryptographic Library with Nested Operations. Backes, Pfitzmann and Waidner.

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

  • Cryptographic Techniques for Privacy-Preserving Data Mining. Pinkas.
  • Paper and discussion of code obfuscation. The link above is to a discussion of the Barak et al. paper, which is available at the bottom of the discussion as reference [1]. Please read both the paper and the discussion.

    • 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

  • Cryptographic Limitations on Learning Boolean Formulae and Finite Automata. Kearns and Valiant.
  • Cryptographic Hardness of Distribution-specific Learning. Kharitonov.
  • When Won't Membership Queries Help? Angluin and Kharitonov.
  • Separating Distribution-Free and Mistake-Bound Learning Models Over the Boolean Domain. Blum.
  • Boosting and Hard-Core Sets. Klivans, Servedio.
  • Cryptographic Hardness Results for Learning Intersections of Halfspaces. Klivans, Sherstov.
  • Cryptographic Primitives from Hard Learning Problems. Blum, Furst, Kearns, Lipton.

    • Cryptography and Algorithmic Game Theory

  • Crytpography and Game Theory. Dodis and Rabin.
  • A Cryptographic Solution to a Game-Theoretic Problem. Dodis, Halevi, Rabin.
  • Rational Secure Computation and Ideal Mechanism Design. Izmalkov, Micali, Lepinski.
  • Cryptography and Mechanism Design. Naor.
  • Privacy-Preserving Auctions and Mechanism Design. Naor, Pinkas, Sumner.

    • Privacy-Preserving Data Mining and Inference

  • Privacy-Preserving Data Mining Bibliography. Liu.
  • Privacy-Preserving Bayesian Network Structure Computation on Distributed Heterogenous Data Wright, Yang.
  • Privacy-Preserving Belief Propagation and Sampling. Kearns, Tan, Wortman.