Reciprocal And Personalized Location Privacy Protection Method Based On K-anonymity

With the popularization of smart phone and the development of positioning technology,Location Based Service(LBS)has been widely applied.However,while enjoying the convenience brought by LBS,users are required to submit their real locations to the Location Service Provider(LSP).Once the submitted locations are collected and abused by a malicious LSP,users will face the risk of privacy leakage.To address this,researchers have proposed various location privacy protection methods.Among them,as a most commonly used method,K-anonymity has been widely concerned due to its advantages such as low computing cost and accurate query results.In the study of K-anonymity,Reciprocity provides high security.All users in the same anonymity set will construct the same anonymous spatial region when they initiate LBS query request,thus effectively resisting inference attacks.However,existing Reciprocity schemes all assume that the privacy needs of users are completey consistent,while in real life,users may have different privacy needs according to their current environment.At this point,if the existing Reciprocity schemes are directly applied,the attacker can obtain the location privacy of users by intercepting and observing the query requests,resulting in the risk of privacy leakage.In conclusion,exsiting K-anonymity schemes fail to address both Reciprocity and personalized LBS,so that cannot satisfy the needs of users.To address the aforementioned problem,we analyze the characteristics of Reciprocity and personalized LBS.Considering that existing schemes fail to combine Reciprocity and personalized LBS,we propose a forest storage structure suitable for personalized privacy requirements in distributed environment,and use this structure to store group division information of users.We design a reciprocal and personalized location K-anonymous privacy protection algorithm,namely PRC(Personalized and Reciprocal Cloaking).Furthermore,we extend it to EPRC(Enhanced PRC)to satisfy continuous request scenarios.The main work of this paper includes:(1)Aiming at the snapshot LBS query,a forest storage stucture suitable for personalized privacy needs of users is proposed.Based on this structure,the PRC algorithm satisfying both Reciprocity and personalized privacy needs is designed.With the target of minimizing the total cost of the anonymous cloaking region construction,combined with the userdefined privacy need,weight of privacy protection and weight of service quality,the proposed algorithm uses the Hilbert curve to index users and divides them into groups in units of anonymity set.All users in the same anonymity set will construct exactly the same anonymous spatial region when they initiate LBS query requests,so as to protect user privacy.(2)Since PRC algorithm does not take into account of user state change while moving,if directly applied to continuous scenarios,it may lead to large anonymous spatial region or overlap,resulting in service quality decline and the risk of privacy leakage.Therefore,we analyze user state change,and divide it into three situations: user join,user leave and user relocation.On the basis of PRC algorithm,we further propose EPRC algorithm.EPRC uses forest storage structure to update user state changes and dynamically adjust anonymity sets to maintain Reciprocity.Even under continuous requests,it can still provide personalized privacy protection service and always construct reciprocal anonymous spatial regions.(3)By means of theoretical analysis,the security and convergence of our scheme are proved,and the complexity of our scheme is calculated to be low.Simulation results show that the proposed scheme has limited area of anonymous cloaking region,communication overhead and computation delay.Compared with the existing Reciprocity schemes which cannot provide personalized service,our scheme brings less cost.The proposed scheme is feasible and effective.