Research On Preserving User's Query Privacy In Location Based Services

With the boom of location-aware mobile electronic devices,Location Based Service(LBS)has recently become popular in almost all social and business fields.To enjoy the LBS,the query user should first submit his current location and query content to the LBS server,then the LBS server searches for his database and returns corresponding results to the query user.However,since the LBS server is always untrusted,he might be able to track the query user according the user's location data,and release the user's sensitive information based on the query content he received.Therefore,how to protect user's privacy in LBS is a problem that should be solved quickly.In addition,the LBS server may be compromised and behave dishonestly,such as returning forged or incomplete results.Therefore,how to verify the validity and integrity of query results efficiently is a vital problem that need to be solved.This paper aim to preserve query user's privacy and verify query results in LBS,and the main contributions are summarized as follows:(1)We propose a location and query content privacy preserving protocol in Location Based Service.Firstly,to preserve the location privacy,we systematically construct a grid-based indexing structure,where LBS server can perform a secure search without knowing any information about query users'location.Secondly,to prevent the LBS server from deducing the content of the query data,we propose a secure query protocol,where data provider can use his self-choosen keys to encrypt his data,query users can generate query conditions without knowing these keys,and LBS server can retrieve results correctly without knowing the actual value of both data provider's and query users' data.Finally,with thorough security analysis and extensive experiments on the real world data sets,we confirm the security and efficiency of our proposed protocol.(2)Based on "dishonestly" LBS server,we further propose a verification protocol against statistical attacks.In particular,we first replicate a portion of the original Points of Interest(POIs)based on their distribution and insert the duplicates into the original datasets,which can disturb the original distribution of POIs,so that the LBS server cannot statistic the real number of POIs in each encrypted grid cells.Second,we use different secrets to encrypt the original POIs and duplicated POIs,which leads to the LBS server cannot know which POI is the verification data,or how many POIs are used for verification.Furthermore,we study the key parameters in our system to improve the verify ability and reduce the overhead of system.Finally,we give rigorous analysis and conduct extensive experiments,which confirms the efficacy of our proposed protocol.