Research On Spatial Search Technology Of Privacy Protection

In recent years,with the development of communication technologies and intelligent terminal equipments such as mobile phones,location-based services(LBS)have been widely used in people's lives.However,in the process of enjoying the location service,users need to send their own location information to the LBS server,so users are starting to worry about their privacy being compromised.So people want their privacy to be protected while enjoying location-based services.Although there are many privacy protection algorithms for location-based services,most of which do not consider that attackers may use the edge information(such as the historical query probability of the location)to obtain the location privacy of users.In this dissertation,we focus on that area,and the main work is as follows:First,a Dummies Generation Algorithm(DGA)is proposed.The DGA algorithm adopts the principle of maximum entropy and the greedy strategy to select location dummy.Considering that it is possible for an attacker to use the historical query probabilities of various locations on the map to filter the possible locations of users,the DGA algorithm proposes and proves a location dummy selection principle based on maximum entropy which is used to select dummies and try to choose the location that is equal to or closest to the historical query probability of the user's real location at each selection of the location dummy.This final location dummy has a similar probability of historical inquiry to the real location,in order to achieve the purpose of confusing the attacker.Second,in order to make the generated dummies not be too concentrated on the user's real position,an enhanced-Dummies Generation Algorithm(E-DGA)is proposed in this dissertation.The E-DGA algorithm considers not only the historical query probabilities of various locations on the map,but also the spatial distribution of each dummy.During the generation of dummies,we take the principle of maximum entropy as a basis and the use of greedy strategy a selection standard of the user's real location with the historical query probability of dummy,in order to achieve the purpose of confusing the attacker.Thirdly,in order to make the dummies be more evenly distributed,a Circle-Dummies Generation Algorithm(C-DGA)is proposed in this dissertation,to select the dummies on these extensions and the dummies based on the principle of maximum entropy,at the same time,with the greedy strategy for further screening.The dummies are eventually generated by the C-DGA algorithm which will be uniformly distributed in a circular region and have similar historical query probabilities.Finally,the performance evaluation of this algorithm is carried out by designing experiment simulation.Experimental results show that DGA algorithm can not only protect the privacy of users but also reduce the total running time of the generated dummy.E-DGA algorithm can achieve the same level of privacy protection as DGA algorithm.Although the total time spent generating dummy is longer than that of DGA algorithm,E-DGA algorithm outperformed DGA algorithm in terms of average distance difference.C-DGA algorithm has the same level of privacy protection as the DGA algorithm and the E-DGA algorithm,and the total time to generate the location dummy is shorter than that of both the DGA algorithm and the E-DGA algorithm.The spatial distribution of the dummy generated by the C-DGA algorithm is more uniform.