The current literature around Information Theoretic Private Information Retrieval (IT-PIR) schemes assume the existence of multiple copies of the database distributed across non-colluding servers. Much of the research seems to be around the servers not communicating with each other but only with the client.

Can the results be improved (or are there known results) ? when the the multiple servers communicate among themselves without breaking the security assumptions (say using multiparty computation) ?


When the servers may collude then if they are all corrupted it's exactly the same as 1-server PIR. Thus, in information-theoretic PIR, it is always assumed that only some subset of the servers are corrupted.

It is unclear to me what you would gain by running MPC between the servers. One possibility is to simulate a single-server PIR with many servers. But this would just cost more.

  • $\begingroup$ ? ​ "When the servers may collude then if they are all corrupted it's exactly the same as" 1-server PIR, since they might-as-well not be different serves. ​ ​ ​ ​ $\endgroup$ – user991 Jul 10 '16 at 6:29
  • $\begingroup$ @RickyDemer Sorry for the typo; I of course meant 1-server PIR. Will edit now. $\endgroup$ – Yehuda Lindell Jul 10 '16 at 7:41
  • $\begingroup$ Information-Theoretic PIR is automatically "considering a threshold of the servers", since 1-server PIR implies oblivious transfer. ​ ​ $\endgroup$ – user991 Jul 10 '16 at 9:02
  • $\begingroup$ @RickyDemer Thanks; I answered this question without thinking too much. I meant to say this, but upon rereading it came out very different. In addition, on second thought, I don't see what can be gained at all by incorporating MPC (of course, I could be wrong). So, I've changed my answer completely. $\endgroup$ – Yehuda Lindell Jul 10 '16 at 9:13
  • 1
    $\begingroup$ MPC seems like it's just an example. ​ There could conceivably be an information-theoretic PIR scheme in which client-server communication is reduced by letting the servers communicate directly (while still assuming at least one server is honest). ​ I don't have any idea of how such a scheme might work, but my only understanding of information-theoretic PIR is that I believe at least some constructions are based on locally decodable codes. ​ ​ ​ ​ $\endgroup$ – user991 Jul 10 '16 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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