Proximity Testing Algorithms for Preserving Location Privacy
Zhang Yi-fa · Jisuanji gongcheng · 2015
Existing privacy preserving proximity testing algorithms usually quantize user s location according to grid size,which makes these algorithms have low accuracy.Aiming at this problem,this paper proposes two accurate and secure proximity testing algorithms.A user transforms location to two parts,the coordinates inside the grid and the grid index,and sends them both after encryption.Then the server computes all possible grids which satisfy the query according to the encrypted coordinates.The user judges whether the two users are in proximity according to the response from the server.Experimental result shows algorithm 1 runs fast and sends fewer messages,algorithm 2 is more secure,but it needs more computation and communication cost,and both users are required to be online.User can choose the more proper algorithm based on his trust in the server,the query performance,and the scenario.