Research On Two Classes Of Private Information Retrieval Schemes

Nowadays,with the rapid development of computers,networks and big data,more and more people need to exchange data and share information through the network.Since the network environment is complicated and it is always full of many unstable and insecure factors,one can not guarantee the user's private information.Therefore,it is necessary to guarantee the privacy of the userPrivate information retrieval(PIR)was introduced by Chor et al.1995.The motiva-tion is that a PIR protocol allows a user to retrieve one of records from a database without revealing the identity of the records form the database server,so that the user's query privacy is protected.Then Chor et al.also proposed a model of PIR:database X stored in a server is viewed as a binary vector {x1,x2,…,x?},where xi?{0,1} and i?{1,2,…,K} is the data index.The size of database X is K.The user sends an query q(i)to the database,requests to inquire the i-th data xi and the database sends xi to the user without knowing any informa-tion of any i.A trivial method for a user to retrieve a data item with PIR is to download the entire database and then look up the desired item.It should be noted that the cost of PIR pro-tocols is usually measured in terms of their communication complexity and storage overhead However,the communication complexity is extremely high in the trivial method.To reduce the communication complexity,there are two solutions.The first one is the information the-oretical PIR scheme,in which the database is replicated on several servers and these servers are non-communicating with each other.Then by accessing k replicated server,any user can retrieve the desired date item with PIR.Meanwhile,each server cannot know the information of i.With lower privacy requirement,the second one is the computational PIR model.It based on the ability to calculate limits and some standard encryption assumptions,considering the privacy in the level of computingBased on the information theoretical PIR,we study two classes of PIR schemes.The main work of this paper is as follows1.For the coded PIR scheme,we construct two classes of binary linear PIR codes and determine their parameters.Furthermore,we also analyze the structure of the recovery sets.Comparing with the existed PIR code,our PIR code has more recovery sets2.For the uncoded PIR scheme,assuming that the severs are not communicating with each other,we investigate the PIR problem from storage constrained database.The known capacity-achieving PIR scheme,proposed by Tandon et al.,has the sub-packetization L=(Nt)tM,where N is the number of servers,M is the number of messages,t?{1,2,...,N}.In this paper,for arbitrary N,M,and t,we design a PIR scheme with a smaller sub-packetization(Nt)tM-1 from the storage constrained servers.Moreover,we prove that the proposed PIR scheme can achieve optimal download overhead.Compar-ing with the PIR scheme that proposed by Attia et al.,we reduce the sub-packetization L by a factor t.