PIR Update

A guest post from Bill Gasarch.

There have been two important NEW results in the field of Private Information Retrieval so its worth reviewing the field and the new results (Some background here).

This post is about Information-Theoretic Private Information Retrieval. We state the problem and five results in order of discovery, with the last two being the recent ones.

PROBLEM: A database is an n-bit string (my wife tells me that databases are more complicated than that). The USER wants to know the ith bit but does not want the DB to have ANY CLUE of which bit he wanted.

EASY ANSWER: Request the ENTIRE DB. That is n bits.
QUESTION: Can we do this with substantially fewer than n bits?
ANSWER: NO if there is only one copy of the database.
NEW QUESTION: What if there are k copies of the DB?

1. 2 DBs, O(n^1/3) bits; for k≥ 4, k DBs O(n^1/k)
   Private Information Retrieval, Chor, Kushilevitz, Goldreich, Sudan, JACM-1998, (Earlier version FOCS 95)

   NOTE: Introduced the field. Journal version has easy constructions. Conference version had slightly harder poly-interpolation constructions material that are a prelude to item (3) below.
   NOTE: FOCS version has O(n^1/k) result, Journal omits it since item 2 below had already appeared.
   NOTE3: k=3 gives O(n^1/3)—can't use that its 3 DB's instead of 2.

2. k DB's, O(n^1/(2k-1))
   Upper Bound on the Communication Complexity of Private Information Retrieval Ambainis, ICALP97,

   NOTE: Used Recursion. Constant is exponential. Later papers that reduced the constant to polynomial lead the way to the next paper.
   NOTE3: k=3 gives O(n^1/5).

3. k DB's, n^{O(loglog k/(k log k))}
   Breaking the O(n^1/(2k-1)) barrier for information-theoretic Private Information Retrieval Beimel, Ishai, Kushilevitz, Raymond. FOCS 02.
   NOTE: Brilliant use of polynomials.
   NOTE3: Techniques yield k=3, O(n^1/5.25)
   

4. 2 DB Ω(n^1/3) LOWER BOUND
   An Ω(n^1/3) lower bound for bilinear group based Private Information Retrieval Razborov, Yekhanin, FOCS 2006.

   NOTE: Hard paper! Modeled 2-DB-Private Information Retrieval via Latin Squares and then used representation theory of finite groups to push through the lower bound. ALL current 2-DB protocols fit the model, so lower bound is either legitimate or will point way to other techniques. My money is on legit. Even so, there aren't that many 2-DB protocols so who knows…

5. 3 DB O(n^1/32,586,658) PIR! Really!
   New Locally Decodable Codes and Private Information Retrieval Schemes, Sergey Yekhanin

   NOTE: Wins award for largest distance between GREATNESS of content and AWFULNESS of title. I would have called it

   A 3 DB O(n^1/32,586,658) PIR! Really!

   NOTE: Uses Mersenne primes. The number used is based on the largest Mersenne prime known, which is 2^32,586,658-1. If there are infinitely many Mersenne primes then, for infinite number of n, get k=3, n^{1/loglog n}-Private Information Retrieval
   NOTE: Vast improvement on k=3, n^1/5.25
   

In the constructions in items (2) and (3) above the k-DB PIR was constructed recursively out of k'-DB PIR's for k'<k. Hence this massive improvement for 3-DB PIRs leads to improvements for these schemes.
PIR scheme (2): the new 3-DB PIR leads to a k-DB, O(n^1/(bk-1)) where b is enormous.
PIR scheme (3): the new 3-DB PIR leads to the same asymptotic k-DB n^{O(loglog k/(k log k)} but with a much smaller constant in the O-of term.