For the second half of the semester, we will cover black box separations, under two topics -- separations, and lower bounds. Below are two groups of papers for the two topics. In the first topic, the papers presented in class will be some subset of the papers (probably not RTV) -- the rest will be for reading. (we already have Mariana as a volunteer for next Thur paper GKMRV). For the second topic, I included a fairly exhaustive list (at least with respect to recent years). I have not yet decided which of these will be presented in class, and in fact we might not even have all of them as an actual recommended reading list. But I am including them all for the students in the class to see, get ready, maybe see if they want to volunteer to present one of these, or want to influence which will be presented in class / read.

A couple of the papers were marked as "counts as 2 papers" -- this means a student can read the paper over two weeks (but should make signficant progress - around half paper -- for the first week already). Papers that were not marked like this, cannot be counted twice, even if they appear on the reading list for two consecutive weeks (e.g., those who read RTV last time, cannot read it again now, and same for future).

People who should still speak in class include: Andrew, Homin, Rajesh, Iasonas (and Mariana but she will be next week). Whatever papers/lectures are not covered by these 4 people, will be covered by me or invited speakers (hoeteck? rosario?).

For next week, the reading list includes the 5 papers in the first list . The "survey" would include the last 4 (without the simon paper). However, I don't want more than two survey people (in general, for any class - so far this has taken care of itself without this as an explicit requirement).

Black Box Separations :

Finding Collisions on a one-way street: Can secure hash functions be based on general assumptions.(Eurocrypt 1998).

Dan Simon.

The Relationship between Public Key Encryption and Oblivious Transfer.(FOCS '00).

Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan.

(presented by Mariana next class)

On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates. (FOCS '01).

Yael Gertner, Tal Malkin, Omer Reingold.

Notions of Reducibility between Cryptographic Primitives. (TCC `04).

O. Reingold, L. Trevisan, S. Vadhan.

Towards a Separation of Semantic and CCA Security for Public Key Encryption (TCC 2007).

Gertner, Malkin, Myers.

(counts as 2 papers)

Black-Box Lower Bounds on Efficiency: check with Tal if you want to read a paper with a *

Limits on the efficiency of one-way permutation-based hash functions* (FOCS 99).

Kim, Simon, Tetali

Bounds on the Efficiency of Generic Cryptographic Constructions*

SIAM Journal on Computing 35(1): 217-246, 2005.

Rosario Gennaro, Yael Gertner, Jonathan Katz and Luca Trevisan

Note: This is the journal version of two separate papers: (counts as 2 papers) Lower Bounds on the Efficiency of Cryptographic Constructions(FOCS 2000).

Gennaro Trevisan

Lower Bounds on the Efficiency of Encryption and Digital Signature Schemes(STOC 2003).

Rosario Gennaro, Yael Gertner, Jonathan Katz

On the impossibility of constructing non-interactive statistically secret protocols from any trapdoor one-way function.*(CT-RSA 2002).

Marc Fischlin

On hardness amplification of one-way functions(TCC 2005).

Lin, Trevisan, Wee

Bounds on the efficiency of black-box commitment schemes(ICALP 2005).

Horvitz and Katz

One-way permutations, interactive hashing, and statistically hiding commitments*(TCC 2007).

Hoeteck Wee

Lower bounds on signatures from symmetric primitives (FOCS 2007).

B. Barak and M. Mahmoody-Ghidary

Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments (FOCS 2007).

Iftach Haitner, Jonathan J. Hoch, Omer Reingold and Gil Segev

slides

A linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval* (TCC 2008).

Haitner, Hoch, Segev

Non-Trivial Black-Box Combiners for Collision-Resistant Hash-Functions don't Exist(Eurocrypt 2007).

Krzysztof Pietrzak