Research And Parallel Implementation Of Nearesr Neigbor Query Protocol In LBS Privacy Based On Goldberg IT-PIR

With the rapid development of emerging technologies such as mobile Internet technology,social network technology and big data technology,the problem of the LBS privacy protetion has become more serious.Compared with the other LBS privacy protection technologies,Private Information Retrieval(PIR)-based privacy protection technology for LBS has higher privacy protection level,provides accurate query results and does not require any trusted third party.However,most of the existing query protocolls based on this technique assume that the LBS server is semi-honest,and waste some communication and computing cost,which caused by resisting pattern attacks.In order to solve these problems and protect the database server under the conditional malicious attack,this paper proposed the protocol of nearest neighbor query based on the protocol of Goldberg's Information-Theoretic Private Information Retrieval(Goldberg's IT-PIR)which has lower computational complexity.The main research work and achievements are as follows:(1)Proposed a nearest neighbor query protocol in LBS privacy based on Goldberg's IT-PIR.In order to solve the problem of the higher cost of communication and computing,which caused by resisting pattern mode,the two level R-tree were constructed,so that the user's different nearest neighbor query can have the same number of PIR visits without adding invalid PIR retrieval to resist the pattern attack.Besides,for the problem of low query efficiency,the Goldberg's IT-PIR protocol was used to retrieve candidate nearest neighbor points online.If the LBS server showed the malicious operation(t servers colluded with each other,l-k servers crashed,v servers returned the wrong results),the protocol can ensure that users can query the correct results safely and efficiently.(2)Achieved the parallelization of query response on LBS server of nearest neighbor query protocol based on Goldberg's IT-PIR.Through the analysis of LBS server-side query response algorithm,we introduced the parallelization of Strassen matrix multiplication algorithm to solve the problem of the low query efficiency,which caused by the large-scale query requests.This algorithm achieved the parallelization of LBS server-side query responses using the multi-threading technology.According to the evaluation standard of the LBS privacy protection technology,we did experiments to analyze the performance and accuracy of the algorithm.The experimental results showed that compared with nearest neighbor query algorithm of Ghinita et al,the communication cost of the proposed algorithm is reduced by about 25%,and the computing cost is reduced by about 87%.In addition,the maximum error of the proposed algorithm is about 0.04%.Finally,the experimental results show that the proposed parallel algorithm can effectively improve the computational efficiency of LBS server when the number of queries is greater than 128.