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
Black Box Separations :
Finding Collisions on a one-way street: Can secure hash
functions be based on general assumptions.(Eurocrypt 1998).
The Relationship between Public Key Encryption and Oblivious Transfer.(FOCS '00).
Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh
(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
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*
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
This is the journal version of two separate papers: (counts as 2 papers)
Lower Bounds on the Efficiency of Cryptographic Constructions(FOCS 2000).
Lower Bounds on the Efficiency of Encryption and Digital Signature
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).
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).
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
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).