# Private Information Retrieval with a pre-prepared database

Informally, Private Information Retrieval (PIR) is a protocol between a user $U$ and a Server $S$, that meets the following conditions:

• $U$ obtains enough information about a database hosted by $S$, to decide which record $i$ in the database to request from $S$.
• $U$ initiates the PIR protocol with $S$ and retrieves all information from record $i$, without $S$ learning this was the record $U$ requested.

The trivial PIR protocol consists in $U$ requesting the entire database from $S$, replicating it locally, and performing all queries locally. The purpose of the more elaborate PIR protocols is consequently to reduce the amount of data that has to be transferred between $U$ and $S$, without $U$ loosing this privacy.

However, from what I understand, all existing PIR protocols still require $U$ and $S$ to transfer data with a quantity that is a function of the size of the entire database, rather than a function of the size of the individual records. (If not for any other reasons, because $U$ has to obtain enough information about the database in advance, to be able to pick $i$.)

I would like to know if it would be possible to reduce the quantity of the data transmitted, by introducing a third party $TP$ and changing the game (exactly) as follows:

• $TP$ obtains the long term public key of $U$. This is the only information exchanged directly between $TP$ and $U$ throughout the entire protocol
• $TP$ decides what information $U$ is to retrieve, prepares it using the long term public key of $U$, and posts it to the database of $S$
• $U$ requests the record posted by $TP$ by sending her long term public key to $S$. $S$ responds and $U$ decodes the response using her long term private key. $S$ doesn't learn which record was requested by $U$.

The trivial protocol that meets these conditions, would be if $TP$ performs a conventional public key encryption of the record, $U$ requests the entire database, attempt to decrypt each record in order, and picks the one that decrypts correctly.

Granted, such a protocol would, in some respects, be significantly different from PIR, so perhaps there already exists a better term for it that I am not familiar with.

-

## 1 Answer

Efficiency of PIR largely depends whether you have a single-server or a multi-server PIR (replicate the database $n>1$ times).

Multi-server PIR seems more attractive (Ian Goldberg does a lot of research into this direction, e.g., this paper is the basis for most multi-server PIR approaches). Considering the database to be organized in a $r\times s$ matrix the client communication function of $r$ and the number of servers and the servers communication a function of $s$.

This is a recent paper on boosting the efficiency when receiving multiple blocks in one query PIR in multi-server PIR.

What you mention (as far as I understand it) is a single-server solution and typically called hardware-assisted PIR (you may look here) and seems to be a practical alternative to multi-server PIR. Here, loosely speaking, you have a trusted component to which you send encrypted queries, this trusted party scans the entire database (typically co-located at the server for performance in form of some hardware secrutiy module) and then sends you back the encrypted query-result.

-
AFAICT, the paper you refer to in your last paragraph describes a protocol where $U$ and $TP$ negotiates the query in real time. I am however interested in a protocol where $TP$ and $U$ do not communicate at all, save for the exchange of long term public keys. That is, $TP$ is able to pick the query without communicating with $U$. – Henrick Hellström Nov 21 '13 at 10:23
Yes, this requires on-line interaction. But as far as I understand it in your approach $S$ will learn which encrypted item (whatever this is) $U$ retrieves and the goal of PIR is to conceal exactly this information. – DrLecter Nov 21 '13 at 10:29
That is incorrect, I am asking for a protocol in which $S$ will not learn which item $U$ retrieves. We might assume the cipher text of the public key encryption is indistinguishable from uniform in the conventional sense. – Henrick Hellström Nov 21 '13 at 10:35
Still don't get it :) If the database (or a part of it) is encrypted for some user, then you perform PIR on an encrypted database. But still, if $U$ does not query the entire database (or use any more efficient PIR), the index $i$ of your "indistinguishable from uniform" string will be leaked to $S$. Maybe you mean that $TP$ prepares a new query result for every single query of $U$ (i.e., stores the encrypted value to $S$ every time), this does not seem to be really practical? – DrLecter Nov 21 '13 at 10:46
I am asking for functions $E$, $F$ and $D$, such that, for a set of records $\{r_j\}$, where, for some $i$, $r_i = E_U(m_U)$, then $m_U = D_U(F_U(\{r_j\}))$. Trivially, if $F$ simply consists in concatenating all records of the encrypted database, then $S$ will not learn $i$ by being asked by $U$ to perform $F_U$ on the entire database. My question is whether there exists more efficient functions. – Henrick Hellström Nov 21 '13 at 10:56