Keywords

3.1 Introduction

The information society is mainly founded on the information and communications technologies (ICTs). The members of the information society want to obtain the information as fast as possible, from everywhere and at any time [1]. Emergency services, LBS reminder, map navigation, location-based marketing, location-based search, and location-based advertisement are examples of location-based services. LBSs are available on a variety of mobile platforms like mobile devices, PDAs, GPS devices, and other devices because they are ubiquitous. Nowadays, the growth of LBS users is very fast. In location-based application, users provide their highly personalized information like their identification information and location information to the service provider causing vulnerability to their privacy, e.g., an attacker can also get the current location of the user and also track user’s daily activities. Due to the tracking capability, it opens many possibilities of computer based crimes like kidnapping, harassment, car theft, and many more. Varieties of attacks are already possible, so there is a big challenge to protect location privacy with minimum cost.

3.2 Literature Survey

In this section, we analyze popular category of crypto-based privacy model for location-based service that has been proposed by different authors.

3.2.1 Categorization of Crypto-Based Privacy Model for LBS

In the simple form of communication between an LBS user and LBS provider, the former sends a simple query (Q) containing an ID and his location (L) and a request for information (I) that he wants to retrieve from provider P [2]. A user provides his identity and location to provider, but provider is not always trust worthy.

Most schemas within this category adopt a centralized model for privacy [3]. There are many solutions that are already proposed by using TTP based schemas [4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]. TTP based schemas are used very often and easy to deploy. This schema has many drawbacks so do not rely on TTP [1]. Many schemas are already proposed as TTP free schemas [20,21,22,23,24].

3.2.1.1 TTP Free Schema

Without the help of trusted third party, all users jointly compute the task which will improve the privacy of the users.

3.2.1.1.1 Collaborative-Based Schema

It is a fully distributed schema. The trust is scattered among the nodes that form an ad-hoc network. All peers work collaboratively as shown in Fig. 3.1 to achieve privacy among untrusted entities. Various algorithms are already proposed by Solanas et al. [7,8,9]. The advantage of this approach is that it does not rely on TTP, it is distributed and also guarantees us privacy, but it has issues with cost and scalability.

Fig. 3.1
figure 1

The communication schema of collaborative method between users and LBS provider [3]

Full size image

3.3 Motivation of Proposed Approach

Many schemas have been already proposed by different authors but they pose and open challenges that need to be solved, such as reducing communication cost, reducing computational cost, and poor scalability. Our aim is to propose a novel solution that provides location privacy to the LBS users. The main goal of the research is to achieve features such as TTP free, hybrid approach (centralized and decentralized), improve scalability, reduce cost in resource constraint devices, collision free, and enhance privacy.

Figure 3.2 represents the system architecture of proposed schema. It contains two main components: (1) LBS users and (2) LBS provider. Each user has their private information on their mobile like UserID U id and location information (Lgi, Lti). There is a need of preserving the privacy of LBS users. As our first step, we are finding the number of Users U i in cloaking region who are requesting for location-based information. Next, we generate random region [25] R i based on the clustering algorithms for users in spatial cloaking region. This procedure creates different cluster as shown in Fig. 3.2. All users will add some random value in their original location information because any malicious user can collude with location-based service provider. To avoid this attack, each user will add random value in their actual location by using secrete share function and perform a secure data aggregation using privacy homomorphism PH [10] in each random region R i which uses centralized approach that is shown in Fig. 3.2 with blue edges. Next, we use the decentralized approach to perform random chaining RC for all distributed random region R i to compute the secure centroid C as shown in Fig. 3.2 with green edges. The last user, U, sends the encrypted sum of location C to LBS provider P as shown in Fig. 3.2 with red edge. LBS provider will decrypt this sum of location by his own private key.

Fig. 3.2
figure 2

Proposed communication schema of hybrid approach between users and LBS provider

Full size image

Algorithm 1 Users Communicate Using Proposed Model

Input: LBS Users Ui (User Identification Uid, Position information (Lgi, Lti)).

Output: Compute Secure Centroid C.

1: Find LBS requesting Users in cloaking region Ui.

2: Create Region Ri using Clustering Algorithms in spatial cloaking region.

3: All users add random noise in their current location using Secret Share function.

4: Perform Secure Data Aggregation using privacy homomorphism [27, 28] PH using Centralized approach in each random region Ri for cloaked area.

5: Perform Decentralized Random Chaining RC for all random region Ri and compute the secure centroid C for cloaked area.

6: The Last User, U send encrypted sum C centroid to LBS provider P.

7: LBS Provider P perform decryption using his own private key and Find Centroid.

The main aim is to hide the user’s location within the other users and also give inaccurate location information to the LBS provider. We use hybrid approach that includes distributed method to achieve minimum cost and improve scalability. In this paper, we propose a protocol schema that preserves privacy between users and LBS provider [26]. Proposed protocol schema is shown in Fig. 3.3.

Fig. 3.3
figure 3

Flowchart for proposed protocol schema

Full size image

3.4 Experimental Results and Evaluation

We have developed the simulation scenario and implemented the same in Java. We evaluated it on an Intel Core i3 2.30 GHz machine with 2 GB of RAM running Windows 7 OS. We experimented the performance with different density based clustering algorithm and different dataset of users. Performance metrics is measured in average computation time taken by the processes.

3.4.1 Datasets

In our simulation, we use dataset of Weeplaces,Footnote 1 which contain check-in activity of the users in location-based social network. It is also integrated with the API of other location-based social network (LSBN) like Facebook place (see footnote 1), Gowalla,Footnote 2 etc. Users have to login in location-based social network and they can connect with the other friends in this network, those who have already registered in this application. This dataset contains 7,658,368 check-ins generated by 15,799 users over 971,309 locations [2]. We use this dataset because users can connect with Weeplaces datasets and connect with their friends. They can also perform location-based search.

3.4.2 Density Based Clustering Algorithms

It is the process of making the groups of points together, which are close for the given dataset/set of points in space. This is called as density based clustering. Examples of density based clustering [29,30,31] are DBSCAN, OPTICS, etc. We use density based clustering algorithm DBSCAN and Optics to create random region in cloaked area.

3.4.3 Results

We have analyzed the performance of our model for various parameters like execution time and number of clusters based on various users as shown in Figs. 3.4 and 3.5 and Table 3.1. OPTICS algorithm gives better results as compared to DBSCAN clustering algorithm.

Fig. 3.4
figure 4

Total execution time over number of users for Weeplaces dataset

Full size image
Fig. 3.5
figure 5

Number of clusters over number of users for Weeplaces dataset

Full size image
Table 3.1 Result of various parameters of Weeplaces dataset
Full size table

3.5 Conclusion

In location-based services, users will get some important information based on their location by providing their highly personalized data like user’s identity, user’s location information, etc. Privacy preservation is of paramount importance with the rapid growth of LBS users. In this paper, we address the benefits and issues of both TTP based and TTP free schema. In our proposed approach we select hybrid tech-nique to take advantage of centralized and centralized schema. This schema gives the guarantee of privacy of the users with improves scalability and reduces the cost. We have created random region from the given set of input dataset by using basic density based clustering algorithms—DBSCAN and OPTICS clustering algorithms. We have analyzed the performance of our model for various parameters like execution time and number of clusters based on various users. OPTICS algorithm gives 60% better result compared to DBSCAN. In future, we will perform homomorphic encryption, construct tree topology, and distributed random chaining approach as per our proposed schema.