Secure Top-k Preference Query for Location-based Services in Crowd-outsourcing Environments

Abstract

This paper considers a practical crowd-outsourcing system model for location-based services which has become increasingly popular due to the rapid proliferation of location-aware mobile devices. In our system, multiple data owners (DOs) outsource their small number of points of interests (POIs) to the location-based service provider (LBSP), then LBSP manages these POIs datasets and allows users to share information and perform top-k queries according to their own preferences. One crucial problem in this system is how to deal with the untrusted LBSP, who may return fake or incorrect query results to users for certain motives. However, the traditional top-k query and verification schemes, where only an individual DO and a single query attribute are considered, cannot be efficiently applied to our system, as users have distinct query preferences and the query may involve multiple DOs. In this paper, we design a dominant authentication graph DAUG) to process the multi-attribute data on multiple datasets efficiently, and two schemes are proposed for users to verify the integrity of the query result based on DAUG. Finally, theoretical analysis and simulation results show our superiority to the previous scheme in terms of effectiveness and efficiency.