Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.