Is there any way to perform Private Information Retrieval when no computations can be executed on the server-side?
I would like to perform the computations on the client, and without having to download the whole database.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Can you be more specific about what you mean by no computations on the server? $\endgroup$– mikeazoJan 20, 2017 at 12:18
-
$\begingroup$ I think that my question is in the context of information theoretic PIR. If I understood correctly, the client needs to encode a query for the server, the server receives the query, applies it to the data (for example a vector matrix multiplication in a particular protocol) and then returns the answer to the client which can decode it. I am constrained in my scenario by the fact that the server acts only as a static storage, without any computational power. $\endgroup$– stefanixJan 20, 2017 at 12:39
-
$\begingroup$ Okay, so let's take a step back for a moment and ignore PIR. How would you retrieve data from that server in that scenario? $\endgroup$– mikeazoJan 20, 2017 at 12:59
-
$\begingroup$ @mikeazo : Presumably, he sends block-numbers to the server, and the server responds with the corresponding data blocks. $\endgroup$– user991Jan 20, 2017 at 19:05
-
1$\begingroup$ @stefanix : Information-theoretic PIR requires more than one server. $\endgroup$– user991Jan 20, 2017 at 19:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Not when it comes to PIR. However, depending on your use case, have you considered using Oblivious RAM?
From Mayberry et al. (2013):
There are traditionally two ways to hide a user’s access pattern (given only a single server/cloud): Oblivious RAM (ORAM) and Private Information Retrieval (PIR). The traditional approach taken by ORAM is to arrange the data in such a way that the user never touches the same piece twice, without an intermediate “shuffle” which erases the correlation between block locations. [...]
Private Information Retrieval, in contrast with ORAM, hides the target of each individual query, independent of all previous queries. This can be accomplished by using a homomorphic encryption which the server uses to operate over the entire database, selecting out the block of data that the user has requested. The user generates encrypted requests and sends them to the server. Since PIR does not try to hide a sequence of accesses, but each access individually, the amortized cost is equal to the worst-case cost. Unfortunately, the requirement that the server computes over the entire database for each query is often impractical, especially for large databases.
So, for ORAM you generally have a single client, which holds some client storage. Of course it is possible to have multiple clients, but then they have to download/re-upload the client state before and after transferring blocks. One construction is Recursive Path ORAM, which for storing $N$ blocks has $O(\log N) \cdot \omega(1)$ blocks of client storage and $O(\log N)$ blocks of bandwidth, where we assume blocks are “moderately sized”, i.e. of size $\Omega(\log^2 N)$.
