Study On The Negative Surveys And Related Applications

The popularity of mobile smart terminals and the rapid development of mobile internet and mobile social network brings people’s life and work great convenience. However, at the same time, they also lead some potential risks to users’private and sensitive information. Researchers have proposed a lot of privacy protection approaches to protect the private and sensitive information of users, including k-anonymity, randomized response technique, negative survey, randomized substitution technique, and so on. The negative survey is a novel privacy protected approach, this approach is inspired by the idea of the negative representation of information, and it has a promising and wide application prospect. Existing works have introduced two kinds of negative surveys and the corresponding methods on estimating positive survey from negative survey, but they did not propose a fast method to estimate positive survey from negative survey quickly. Hence, we propose a fast method called fastNStoPS to estimate positive survey from negative survey quickly, and we also propose a method to search optimal negative surveys based on fastNStoPS. Moreover, the negative survey can be applied to protect the location privacy and trace privacy of users. However, to our best knowledge, no work has focused on analyzing and proving the effectiveness of protecting location privacy and trace privacy for the negative survey in theory. Therefore, we give the detailed analyses and proofs for the effectiveness of applying single selection negative survey to protect location privacy and trace privacy in this thesis, we also give the secure length of the moving object’s trace by using multiple selections negative survey to protect location privacy and trace privacy.Specially, the main work in this thesis includes the following aspects:(1) We propose an approach called fastNStoPS to decrease the number of iterations based on the Steffensen method, and fastNStoPS is used to estimate positive survey from negative survey. In existing papers, researchers have proposed two estimation approaches:the inversion approach and the iteration approach. The inversion approach is invalid when the transformation matrix is irreversible, moreover, the results obtained from the inversion approach could contain negative values, and this does not agree with the fact. The computing cost of the iteration approach is very high when the number of samples is large. Hence, we propose fastNStoPS, and we model searching optimal negative surveys as a multi-objective optimization problem based on fastNStoPS, and the objectives are privacy and utility. Then, differential evolution (DE) is applied to solve the optimization problem, and the pareto front is plotted in a two dimensional space. Users can choose a proper negative survey on the pareto front according to their demands.(2) Horey et al. applied negative survey to protect users’ location privacy and trace privacy, they used a quad-tree to represent users’location. But to our best knowledge, no work has focused on analyzing and proving the effectiveness of applying negative survey to protect location privacy and trace privacy in theory. Hence, first, we give the formalized definitions of location privacy and trace privacy, second, we give the analyses and proofs of the effectiveness of applying negative survey to protect location privacy and trace privacy, and we also give the secure length of users’ trace.We propose a method called fastNStoPS to estimate positive survey from negative survey, and apply DE to search for optimal negative surveys based fastNStoPS. The experimental results prove that fastNStoPS has a good performance and we can find optimal negative surveys. Moreover, We analyse and prove the effectiveness on protecting location and trace privacy for single selection survey, and we also give the secure length of the trace for multiple selections negative survey, users can choose a proper setting according to their requirements.