- If there is just one copy of the DB and there are no comp. constraints on the computational power of the DB then ANY protocol requires n bits comm.
- If there is one copy of the DB then, with some comp constraints, you can do better. I state one result: if quadratic residue is hard then there is a protocol using n^epsilon bits of comm. (Kushilevitz and Ostrovsky). The rest of this post is about the info-theoretic case, so the DB has no comp. constraints.
- If there are two copies of the DB then there is a protocol that uses n^{1/3} bits. (Chor, Kushilevitz, Goldreich, Sudan)
- If there are three copies of the DB then there is a protocl that uses n^{1/32582658} bits. Really! (Yekhanin).
- If a 2-server protocol is a bilinear-group protocol (which all prior constructions were) then it must take n^{1/3}.(Razborov and Yekhanin)
- Most known constructions put into a geometric framework (Woodruff and Yekhanin).

The barrier result was only for a certain type of PIR. It DID cover all the known PIR schemes at the time. But it does not cover this one.

This is how Barrier SHOULD work--- they should not discourage, but they should point to difficulties so that someone can overcome them.

Also note, the new result used the some of the Framework of Woodruff and Yekhanin. So good to unify and obtain new proofs of old results.

## No comments:

## Post a Comment