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.