PENN CIS 620, FALL 2007: FOUNDATIONS OF CRYPTOGRAPHY [PDF]

I will structure the broad discussion and lecture a bit, but each week there will be one or more designated discussants

5 downloads 12 Views 41KB Size

Recommend Stories


part 1, fall 2007: foundations of sociocultural anthropoogy
Never let your sense of morals prevent you from doing what is right. Isaac Asimov

vSphere 6 Foundations 2V0-620 Dumps PDF Download
And you? When will you begin that long journey into yourself? Rumi

PDF, 620 Ko
Before you speak, let your words pass through three gates: Is it true? Is it necessary? Is it kind?

penn distributing co. 2018 fall, harvest & halloween
Where there is ruin, there is hope for a treasure. Rumi

SYST 620 (PDF)
Never let your sense of morals prevent you from doing what is right. Isaac Asimov

CIS 520, Machine Learning, Fall 2015
Ask yourself: Is conformity a good thing or a bad thing? Next

PDF-Download- Applied Cryptography
Where there is ruin, there is hope for a treasure. Rumi

620
When you do things from your soul, you feel a river moving in you, a joy. Rumi

Fall Final Ranking 2007's
The wound is the place where the Light enters you. Rumi

PDF Applied Cryptography
Don’t grieve. Anything you lose comes round in another form. Rumi

Idea Transcript


PENN CIS 620, FALL 2007: FOUNDATIONS OF CRYPTOGRAPHY Prof Michael Kearns [email protected] 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.

Smile Life

When life gives you a hundred reasons to cry, show life that you have a thousand reasons to smile

Get in touch

© Copyright 2015 - 2024 PDFFOX.COM - All rights reserved.