The emergence of mobile devices with fast Internet connectivity and geo-positioning capabilities has le d to a revolution in customized location – based services (LBS) , where users are enabled to access information about points of interest (POI ) that are relevant to their interests and are also close to their geographical coordinates. Pro b- ably the most important type of queries that involve location attributes is represented by nearest – neighbor (NN) queries, where a user wants to retrieve the k POIs (e.g., restaurants, museums, gas stations) that are nearest to the user’s current location ( k NN). Furthermore, keeping such information up – to – date and relevant to the users is not an easy task, so the owners of such datasets will make the data accessible only to paying customers. Users send their current location as the query parameter, and wish to receive as result the nearest POIs, i.e., nearest – neighbors (NNs). But typical data owners do not have the technical means to support processing queries on a large scale, so they outsource data storage and querying to a cloud service provider. Many such cloud providers exist who offer powerful storage and computational infrastructures at low cost. However, cloud providers are not fully trusted, and typically behave in a n honest – but – curious fashion. Specifically, they follow the protocol to answer queries correctly, but they also collect the locations of the POIs and the subscribers for other purposes. Leakage of POI locations can lead to privacy breaches as well as financial losses to the data owners, for whom the POI dataset is an important source of revenue. Disclosure of user locations leads to privacy violations and may deter subscribers from using the service altogether. In this abstract, we propose a family of techniques that allow processing of NN queries in an untrusted outsourced environment, while at the same time protecting both the POI and querying users’ positions. Our techniques rely on mutable order preserving encoding (mOPE), the only secure order – preserving encryption method known to – date. We also provide performance optimizations to decrease the computational cost inherent to processing on encrypted data, and we consider the case of incrementally updating datasets. We present an extensive performance evaluation of our techniques to illustrate their viability in practice.
You are here: Home / ieee projects 2014 / K-NEAREST NEIGHBOUR QUERY PROCESSING IN UNTRUSTED CLOUD ENVIRONMENTS