Forward-secure K Nearest Neighbor Query On Geographical Data

In recent years,the Internet of Things(Io T)has been developed rapidly.Data with location tags are collected by various hardware devices for central management.To alleviate the burden of handling on clients,there is a trend to combine Io T and cloud computing which owns capabilities of strong computing and large-scale storage.Due to unpredictable cyberattacks on public clouds,users usually encrypt their data before subcontracting it to the public clouds.It can protect data from the leakage of private information in such a manner.Since traditional encryption algorithms do not support operations of searching on the encrypted data,various searchable encryption schemes have been proposed in the literature.However,these schemes generally do not support forward security.It results in that the security of the encrypted data cannot be guaranteed in the case of the leakage of query token.Specifically,the adversary can even derive all the plaintext data by investigating access patterns,which are leakage during illegal queries caused by the leakage of the query token.Therefore,to overcome the above flaws,this thesis proposes a new forward-secure searchable encryption scheme on geographically encrypted data,which can preserve user's privacy in k nearest neighbor(k NN)query,including data addition,deletion and updating.First,to build an index structure for speedup query,this thesis uses the locality sensitive hashing(LSH)function to perform hash quantization on a geographical dataset.Data points with the same hash value are gathered into the same hash bucket.To ensure the indistinguishability between buckets,a greedy merge algorithm is proposed in this thesis.Besides,based on the hash bucket,a data structure called average bucket is constructed in this thesis,which is obtained by the greedy merge algorithm.After the k NN query,the keys of the average buckets touched during the k NN query are refreshed to ensure the forward security.Furthermore,this thesis combines a forward index and an inverted index to construct a secure index structure called forwardly inverted dictionary,which can realize the fast location of the candidate set,data addition,deletion and updating.Finally,this thesis designs a dynamic adaptive SD-KNN query scheme based on multiple LSH functions,which can optimize query efficiency and ensure query accuracy through the feedback of query results.The scheme can support users to perform efficient forward-secure k NN queries on encrypted data with location tags.The correctness and security of the scheme are proved through theoretical analysis.Besides,the computational complexity of the scheme is also analyzed in this thesis.Finally,extensive experimental studies are performed on both real and synthetic datasets.By observation,the scheme has a good performance in terms of result accuracy and time efficiency.In conclusion,the scheme is suitable for forward-secure k NN query scenarios on geographical data.