The Capacity Of Private Information Retrieval

With the increasing dependence of social life on the Internet,personal data is collected and used by the service platform consciously or unconsciously,which brings great convenience,but at the same time,these user data contain a lot of sensitive privacy information,once leaked,it will have serious consequences of illegal use,so protecting data security and maintaining user privacy are faced with great challenge.At first,the research on data security mainly focuses on removing sensitive information in public content.Then,with the deepening of the understanding of privacy,some researchers turn their attention to the direct protection of the retrieval target in the process of information retrieval.This problem is called private information retrieval(PIR).The scene is that users retrieve a certain content stored in public databases while protect the index of the content from the databases.Based on this premise,this paper makes an in-depth study on different scenarios of PIR with additional privacy requirements.In the scenario that some databases may give erroneous responses,i.e.,there exist byzantine databases,the capacity of multi-round retrieval is obtained,and an achievable scheme is proposed.The main idea of the scheme is to retrieve all data with MDS code that can detect all errors in the first round,and to identify all the byzantine databases in the following rounds with MDS code that can correct all errors.The user can finally decode the desired messages by ignoring all the answers from the byzantine databases.By using multi-round retrieval scheme,the capacity of private information retrieval from byzantine databases is greatly improved,which is equivalent to increasing the number of effective databases.In the scenario that some databases can collude to analyze the retrieval objectives of users,the retrieval capacity and an achievable scheme under any collusion pattern is obtained.The methods and tools used include the submodular property of entropy function,and linking the download rate and converse proof with the optimal solutions of two linear programming problems.By using the duality of linear programming problems,the final capacity is obtained.The previous researches mainly focused on the special collusion pattern,this paper obtains the effective general retrieval capacity formula and the common performance limit proof for arbitrary collusion pattern,which fills up the lack of understanding of the arbitrary collusion pattern.In the scenario that the databases can arbitrarily collude,and the database needs to protect the security of other contents from users,the capacity and the minimum value of random data that needs to be shared in advance is found out.The retrieval scheme is also based on the optimal solution of the linear programming problem,which allocates the number of retrieval requests sent to each database in proportion.The databases will add a linear combination of random values to the answers,so that the index of the desired messages and the privacy of other messages are protected at the same time.In this paper,symmetric private information retrieval is discussed under a more general collusion pattern,which solves the complex problems in the presence of multiple privacy requirements.