Private Information Retrieval

on

Private Information Retrieval(PIR) is a protocol that allows users to retrieve an element from the database without revealing the database administrators which element has been retrieved. The study of PIR is motivated by the growing concern of users privacy in querying the large databases.

Non Private protocol

In a non-private protocol, the user generally sends the index i of the element that he/she interested in and the databases return the element at the index. In this scenario, the database owners knew what data item has been requested by the user. 

Trivial PIR

A typical solution for this can be like whenever a user sends a request, return the entire database to the user. The user can read whatever he wishes. Privacy is perfect in this situation.


This might not be an efficient solution. Imagine searching google this way. You get back an entire Internet.Apart from privacy, we need non-triviality. The communication cost must be in O(n) where n is the total number of bits in the database.

Alternate Approaches

1. Information Theoretic PIR
2.Computational PIR

In this article, let's concentrate on Information Theoretic PIR.

Information Theoretic PIR

As distributed databases can be seen in applications, this technique assumes that there are 2 or more replicas of a database.

Two Database Approach

Let S denote the subset of n bits of the database. Assume there are two databases of same content DB1 and DB2. Let's say the user needs bit x(i), the element at the index i. The user sends  S to DB1 and S XOR i to DB2.  Each of the two databases, when receiving the message P, a subset of n returns the XOR of bits with the indices in P. Now the user performs the XOR operation of the results from the two databases and finally obtains x(i), the desired output.
           Privacy can be maintained in this case assuming that the two databases do not collude with each other. Communication complexity is O(n^t) where t =1/3.
 

A multi-Database Approach

The two database approach discussed above can be generalized such that it allows the user to obtain required results by querying  2 ^ d databases where d >= 1. The idea is to treat n as a d dimensional cube. This approach is converting 2 database approach to higher dimensions(here d dimensions).

There are several variants of Information Theoretic PIR whose complexity is <<n.

In Computational PIR approach, there is only a single database. The complexity of this approach is sub-polynomial.

Conclusion

Private Information Retrieval provides required privacy to the user with the help of different approaches. There is another verticle of PIR called Strict PIR (SPIR). SPIR takes measures such that user is not provided with an entire database but with what is required. Here the privacy of both the user and the database is maintained.


References

Comments

Post a Comment