Efficient Privacy-Preserving Protocol for k-NN Search over Encrypted Data in Location-Based Service
With the development of mobile communication technology, location-based services (LBS) are booming prosperously. Meanwhile privacy protection has become the main obstacle for the further development of LBS. The k-nearest neighbor (k-NN) search is one of the most common types of LBS. In this paper, w...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2017-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2017/1490283 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832554793941336064 |
|---|---|
| author | Huijuan Lian Weidong Qiu Di Yan Zheng Huang Jie Guo |
| author_facet | Huijuan Lian Weidong Qiu Di Yan Zheng Huang Jie Guo |
| author_sort | Huijuan Lian |
| collection | DOAJ |
| description | With the development of mobile communication technology, location-based services (LBS) are booming prosperously. Meanwhile privacy protection has become the main obstacle for the further development of LBS. The k-nearest neighbor (k-NN) search is one of the most common types of LBS. In this paper, we propose an efficient private circular query protocol (EPCQP) with high accuracy rate and low computation and communication cost. We adopt the Moore curve to convert two-dimensional spatial data into one-dimensional sequence and encrypt the points of interest (POIs) information with the Brakerski-Gentry-Vaikuntanathan homomorphic encryption scheme for privacy-preserving. The proposed scheme performs the secret circular shift of the encrypted POIs information to hide the location of the user without a trusted third party. To reduce the computation and communication cost, we dynamically divide the table of the POIs information according to the value of k. Experiments show that the proposed scheme provides high accuracy query results while maintaining low computation and communication cost. |
| format | Article |
| id | doaj-art-af495657ba2d47378d23dad81425bd49 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2017-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-af495657ba2d47378d23dad81425bd492025-02-03T05:50:32ZengWileyComplexity1076-27871099-05262017-01-01201710.1155/2017/14902831490283Efficient Privacy-Preserving Protocol for k-NN Search over Encrypted Data in Location-Based ServiceHuijuan Lian0Weidong Qiu1Di Yan2Zheng Huang3Jie Guo4School of Cyber Security, Shanghai Jiao Tong University, Shanghai 200240, ChinaSchool of Cyber Security, Shanghai Jiao Tong University, Shanghai 200240, ChinaDepartment of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, ChinaSchool of Cyber Security, Shanghai Jiao Tong University, Shanghai 200240, ChinaSchool of Cyber Security, Shanghai Jiao Tong University, Shanghai 200240, ChinaWith the development of mobile communication technology, location-based services (LBS) are booming prosperously. Meanwhile privacy protection has become the main obstacle for the further development of LBS. The k-nearest neighbor (k-NN) search is one of the most common types of LBS. In this paper, we propose an efficient private circular query protocol (EPCQP) with high accuracy rate and low computation and communication cost. We adopt the Moore curve to convert two-dimensional spatial data into one-dimensional sequence and encrypt the points of interest (POIs) information with the Brakerski-Gentry-Vaikuntanathan homomorphic encryption scheme for privacy-preserving. The proposed scheme performs the secret circular shift of the encrypted POIs information to hide the location of the user without a trusted third party. To reduce the computation and communication cost, we dynamically divide the table of the POIs information according to the value of k. Experiments show that the proposed scheme provides high accuracy query results while maintaining low computation and communication cost.http://dx.doi.org/10.1155/2017/1490283 |
| spellingShingle | Huijuan Lian Weidong Qiu Di Yan Zheng Huang Jie Guo Efficient Privacy-Preserving Protocol for k-NN Search over Encrypted Data in Location-Based Service Complexity |
| title | Efficient Privacy-Preserving Protocol for k-NN Search over Encrypted Data in Location-Based Service |
| title_full | Efficient Privacy-Preserving Protocol for k-NN Search over Encrypted Data in Location-Based Service |
| title_fullStr | Efficient Privacy-Preserving Protocol for k-NN Search over Encrypted Data in Location-Based Service |
| title_full_unstemmed | Efficient Privacy-Preserving Protocol for k-NN Search over Encrypted Data in Location-Based Service |
| title_short | Efficient Privacy-Preserving Protocol for k-NN Search over Encrypted Data in Location-Based Service |
| title_sort | efficient privacy preserving protocol for k nn search over encrypted data in location based service |
| url | http://dx.doi.org/10.1155/2017/1490283 |
| work_keys_str_mv | AT huijuanlian efficientprivacypreservingprotocolforknnsearchoverencrypteddatainlocationbasedservice AT weidongqiu efficientprivacypreservingprotocolforknnsearchoverencrypteddatainlocationbasedservice AT diyan efficientprivacypreservingprotocolforknnsearchoverencrypteddatainlocationbasedservice AT zhenghuang efficientprivacypreservingprotocolforknnsearchoverencrypteddatainlocationbasedservice AT jieguo efficientprivacypreservingprotocolforknnsearchoverencrypteddatainlocationbasedservice |