An incentive mechanism for K-anonymity in LBS privacy protection based on credit mechanism

Abstract

In the location-based service (LBS) privacy protection, the most common and classic solution is K-anonymity, however, existing schemes rarely consider the issue that whether other mobile users are willing to provide assistance to the requesters to form the K-anonymity set, thus leading to their poor practicability. In this paper, an incentive mechanism based on credit is introduced into the distributed K-anonymity, and only providing assistance to the others, a user can gain and accumulate his credit. Based on the fuzzy logic in the soft computing, a probability threshold is introduced to reflect a user’s reputation, and only when a user’s reputation reaches this threshold, can he get the assistance from other neighbors. Security analysis shows that our scheme is secure with respect to various typical attacks. And because of not relying on a trusted third party, our scheme can avoid the security issue resulting from its breach. Extensive experiments indicate that the time to form the anonymity set is short and it increases slowly as the value of K increases. Finally, the additional traffic introduced by this scheme is very limited.

1 Introduction

With the explosive increase of mobile devices with the positioning function, location-based service (LBS) is becoming more and more popular (Hu et al. 2013), since it provides information and entertainment service based on geographical position of mobile devices. There have been more successful LBS cases, such as Foursquare, Google Latitude, Baidu Map, etc. In Foursqueare, which is one of the most popular LBSs, users can check in at the participating businesses for exchanging coupons or gaming rewards, such as badges and mayorships. A recent report¹ shows that 74 % of smartphone owners over the age of 18 use LBSs through cell phones. However, several threats concerning location privacy of mobile users in mobile computing come with the convenience of widely used technique. In LBSs, mobile users have to submit a LBS request including their exact location and identifiers to cloud providers to obtain corresponding queried information. In this case, the user’s individual privacy either is explicitly exposed or can be inferred from other data. For example, when a user queries the nearest hospital frequently, the user may disclose his health information; when a user often searches for business information on certain routes, the user may divulge behavioral trajectory information and so on.

To deal with these challenges, a lot of work (Bamba et al. 2008; Chow et al. 2009; Gedik and Liu 2008; Paulet et al. 2012; Lien et al. 2005; Jung and Li 2013; Ficco et al. 2014) have been done in the field of LBS privacy protection. Among the proposed solutions, the K-anonymity (Gruteser and Grunwal 2003) is the most important technique. It expands the precise position of the querier to an anonymity area including the other K-1 users, and the constructed area is used by the user to initiate the LBS request. The K-anonymity is mainly divided into two categories: the centralized one based on a trusted third party anonymity agent (Bamba et al. 2008; Gedik and Liu 2008) and distributed one without the trusted third party. We focus on the latter, where the LBS requester interacts with other K-1 neighborhood users to form an anonymous area. However, in the practical LBS scenarios, nodes move frequently and do not trust each other. If a node provides assistance to its neighbors, it has to communicate with them, which will consume its traffic and energy. And even worse, the interactive messages may contain the node’s location information, resulting in a possible privacy leakage. Meanwhile, even if a node provides assistance to others, it cannot get any benefits from this. Therefore, the nodes usually refuse to provide assistance to others, resulting in that the LBS requester cannot construct the K-anonymity set, thereby failing to get the anonymous service. Consequently, so far many research results cannot be realized in practical applications (Yang et al. 2013).

To solve the problems mentioned above, the incentive mechanism is introduced into the LBS location privacy protection, and an incentive scheme for the distributed K-anonymity is proposed, which is based on the credit mechanism. A credit certificate is generated for a user in each transaction, and it is stored locally and maintained by the user himself. Based on the credit certificate, a user’s reputation is introduced, and if his reputation is good other users are willing to provide assistance to him. However, a great challenge is how to evaluate a user’s reputation by using the credit value. Fortunately, unlike conventional computing, soft computing (Ahmad and Ansari 2012; Metre et al. 2012) provides an inexact solution to achieve tractability, robustness and low solution cost, which is tolerant of imprecision, uncertainty, partial truth and approximation. Furthermore, fuzzy logic in soft computing is able to handle the concept of partial truth, where the truth value may range between completely true and completely false. Therefore, based on the fuzzy logic, we devise a probability threshold to reflect a user’s reputation. Before each transaction, the originator of a LBS request will deliver his credit certificates to other users. Only when his reputation reaches the probability threshold, would the other neighbors provide assistance to him. In this way, the users are promoted to take an active part in providing assistance to others to form the K-anonymity set.

Our contributions are as follows:

• 1. For the first time, we introduce the credit-based incentive mechanism into the LBS privacy protection, based on which we devise a scheme that promotes users to actively participate in the construction of the K-anonymity set. The users’ credit can be accumulated, which gives them continuous motivation, enhancing the practicality of the distributed K-anonymity.

• 2. Security analysis shows that the proposed scheme is secure against various attacks, including the fake, replay and collusion attack, and it also has the ability to avoid free-riding behavior (Adar et al. 2000). Compared with the unique K-anonymity incentive scheme (Yang et al. 2013), our scheme has several advantages.

• 3. A wireless network testbed is built on which the proposed scheme is examined. Extensive experiments show that the time needed to generate the anonymous area is short and it grows slowly with the increase of the number of users, and the additional traffic introduced is limited.

2 Related work

2.1 Incentive mechanism in LBS privacy protection

Incentive mechanisms are widely used in various fields, and a lot of works have been done in the P2P networks recent years. Incentives are mainly based on the following three mechanisms: direct reciprocity, micro-payment and credit.

Currently, Yang et al. (2013) has introduced incentives mechanism based on direct reciprocity into the LBS scenario, its basic idea is that the nodes in the networks can get some direct benefits through providing services to other nodes. This scheme relies on the auction model proposed by Levin and LaCurts (2008), and by now it is the only one that has introduced an incentive mechanism based on mutual incentives for LBS privacy protection. Because this scheme just considers the direct reciprocity in the current transaction and only stores the current session information, therefore, its most important advantage is that it operates in real-time. However, because the relevance between transactions is not taken into consideration, this incentive mechanism is only suitable for the scenarios where a single transaction lasts long and participants are relatively fixed. However, in LBS nodes always move very frequently, so they are not relatively fixed and they do not take part in continuous transactions. Consequently, this incentive mechanism is not suitable for the LBS scenario.

As a reliable incentive method, micro-payment-based incentive mechanism has got a certain application in P2P networks. Different benefits are got according to network nodes’ respective contributions, thereby encouraging a node to take an active part in networks cooperation. Golle et al. (2001), who first introduces the idea in networking scenarios, uses the game theory to prove the effectiveness of the incentive mechanism to the network. However, this method requires a central server to take charge of the release, distribution and circulation of the virtual currency, so the server’s performance and security bottlenecks are issues to be addressed. Therefore, its feasibility is poor and it is unsuitable for LBS applications. Furthermore, until now there have been no works that apply micro-payment to LBS privacy protection.

The first application of credit-based incentive mechanism appears in KaZaA² which is a file sharing system in P2P networks. Its basic idea is that: (1) a node gets its credit value based on its historical behavior; (2) after one transaction, nodes acquire new credit value by evaluating each other; (3) in the subsequent transactions, different service will be provided to the nodes according to their respective credit level, thereby promoting users to actively participate in the transactions to accumulate credit value. Therefore, it can be noticed that the incentive mechanism based on the credit is suitable for scenarios involving large-scale networks, where transactions are infrequently repeated between nodes. Furthermore, the characteristics of cumulative credit just fit the LBS scenario where nodes move frequently. In this paper, the credit value of a node is stored locally in the form of the credit certificate, which is maintained and updated by the node itself. A semi-trusted third party, i.e., a cloud server, is employed to guarantee the freshness of the credit certificate generated. In the transactions, a node will choose to agree or refuse to provide assistance to the requester according to the latter’s credit. In this way, nodes are promoted to actively take part in the K-anonymity set.

2.2 Soft computing-based LBS privacy protection

Soft computing makes use of inexact solutions to deal with computationally hard problems in polynomial time, which is tolerant of imprecision, uncertainty and approximation. Several location application schemes based on soft computing, such as indoor localization and privacy protection in LBS, are presented.

Through the collection of received signal strength, Trawinski et al. (2013) introduced soft computing to cope with the curse of dimensionality during the process of the feature extraction, and proposed a fuzzy rule-based multiclassification system. Furthermore, since they employed the multiclassifier, their proposed topology-based WiFi indoor localization scheme could provide more accurate localization result. Hernandez et al. (2014) proposed a novel location-aware access control mechanism to avoid the abuse of the resources and services in smart buildings. In their scheme, the magnetic filed measurement is presented to provide the accurate smartphones’ magnetometer, and the users’ location data is estimated by means of Radial Basis Function Networks (RBF). Tang et al. (2015) pointed out that the generated fake trajectories could coincide with users’ real trajectories in LBS. Then, they put forward four principles for the generation of dummy locations, and devised a dummy-based long-term location privacy protection algorithm, which was built on soft computing to balance the user’s preferred privacy protection and computation cost.

3 The scheme model and the format of credit certificate

3.1 The scheme model

The paper is based on the model of distributed K-anonymity, and the credit-based incentive mechanism is introduced. A user that issues a LBS request with a privacy protection demand is denoted as the consumer C. First, C issues a broadcast message to nearby users, requesting them to participate in the construction of anonymity area. Upon receiving the request, a user will reply a message if he is willing to join in the K-anonymity set. Such a user is represented by the service provider S. Meanwhile, there is also a cloud server (Cloud), which is a semi-trusted third party. The model of the scheme is shown in Fig. 1, where the credit certificates of C and S are stored and maintained by nodes themselves.

Fig. 1

The scheme model

We assume that:

• 1. Service requester C and service provider S are not trusted, and they may collude with each other.

• 2. The cloud server is semi-trusted, that is, it will faithfully execute the devised protocol, but it is interested in the user’s privacy information. In addition, it will not collude with C or S.

• 3. The security channels between C and Cloud, S and Cloud have been established when they register with the cloud.

3.2 Format of credit certificates

In the above model, the credit values are stored locally in the form of credit certificates, and they are maintained and updated by the nodes themselves. In each transaction, a node will generate a credit certificate, whose format is shown in Table 1. A node’s old certificate list includes all the old credit certificates generated in the historical transactions.

Table 1 Credit certificate CC format

Each node, as well as the cloud server, has its own public key certificate.

For a node, each transaction will produce one credit certificate. The certificate contains the following fields: (1) the node’s identity $ID_1$ and the other side’s identity $ID_2$; (2) the node’s current transaction number $\mathrm{TID}_n$, which is a number starting from 1; (3) the role flag RF, which denotes the role (“consumer” or “service provider”) that the node plays in the transaction; (4) the signature of the node itself $\mathrm{Signature}_1$, the Cloud’s signature $\mathrm{Signature}_{Cl}$, the other side’s public key and its signature $\mathrm{Signature}_2$. The generation and verification of the certificates are carefully described in details in Sect. 4.2.

4 The proposed scheme

4.1 Certificate generation

It is assumed that C performs a LBS query using K-anonymity and it requests the neighbor nodes to provide assistance for building an anonymous set, and S accepts the request. C’s upcoming transaction number is assumed to be n+1 and S’ upcoming transaction number is assumed to be m+1. In the following, we take the party C as an example to explain the generation of the certificate.

The new certificate generated for the upcoming transaction by C:

$$\begin{aligned} \begin{aligned} CC_{C-\mathrm{new},n+1}&=ID_C \parallel \mathrm{TID}_{n+1} \parallel RF_{n+1} \parallel ID_S\parallel \\&\quad \mathrm{Sign}_C (ID_C\parallel \mathrm{TID}_{n+1}\parallel RF_{n+1}\parallel ID_S) \end{aligned} \end{aligned}$$

(1)

The certificate including the signatures of C and Cloud in C’s (n+1)th transaction:

$$\begin{aligned} CC_{C-Cl,n+1}=CC_{C-\mathrm{new},n+1} \parallel \mathrm{Sign}_{Cl}(CC_{C-\mathrm{new},n+1}) \end{aligned}$$

(2)

C’s final credit certificate after the transaction with S:

$$\begin{aligned} CC_{C,n+1}=CC_{C-Cl,n+1}\parallel \mathrm{Sign}_s (CC_{C-Cl,n+1}) \end{aligned}$$

(3)

The old certificate list of C:

$$\begin{aligned} CC_{C-\mathrm{old}}\mathrm{list}=CC_{c,1} \parallel CC_{c,2} \parallel \ldots \parallel CC_{c,n} \end{aligned}$$

(4)

4.2 The interaction process of the scheme

The interaction process of our scheme is shown in Fig. 2, it mainly consists of four stages, which are: query, two rounds of verifications and the transaction. In the first round of verification, C and S mutually verify the other side’s new generated certification for the upcoming transaction. In the second round of verification, S verifies C’s old certificate list. The specific interaction process is as follows:

• 1. The query stage

When C intends to initiate an anonymous LBS inquiry service, it firstly issues a query request to the nearby neighbors in the form of broadcast. When a node receives this request, if it is willing to join the anonymous set, it replies C with a response message and then the node becomes a service node S. When C receives all the response messages, it constructs the list of service nodes, and is ready to begin the verification process.

Fig. 2

The interaction process of the scheme

• 2. The first round of verification

C generates a new credit certificate CC$_{C-\mathrm{new},n+1}$ for its upcoming $(n+1)th$ transaction, in which the transaction number field $\mathrm{TID}_{C,n+1}$ is the unique identifier of the transaction (it is assumed that C’s last transaction number is n). The role flag $RF_{c,n+1}$ is set as 1, indicating that C is the consumer in this transaction. C generates a new certificate CC$_{C-\mathrm{new},n+1}$ after signing the above information with its private key.

To ensure the security of our scheme, we have to guarantee the continuity and freshness of the transaction number $\mathrm{TID}$. A semi-trusted third party cloud server is employed to store each node’s current $\mathrm{TID}$ value.

Instead of sending CC$_{C-\mathrm{new},n+1}$ directly to S, C transmits them to the cloud server. The latter will first inquire the corresponding node according to the node’s identity, and then verifies the continuity and freshness of its $\mathrm{TID}$ (i.e., to verify whether the $\mathrm{TID}$ in the certificate is the current $\mathrm{TID}$ stored in the cloud plus 1). Moreover, the cloud will check the role flag to ensure that it is set as 1. After a successful verification Cloud signs this certificate, generates CC$_{C-Cl,n+1}$ and then forwards it to S. Upon receiving the message from the Cloud, S will temporarily store the new certificate after a successful verification of the signatures in the certificate. At the same time, S will generate its own credit certificate CC$_{S-\mathrm{new},m+1}$ for this transaction, whose process is same as C’s. S is assumed to have completed m transactions with other nodes, therefore, in its new certificate the transaction number is m+1. In addition, because S behaves as a service provider in this transaction, its role flag is set as 0. When Cloud receives the certificate CC$_{s-\mathrm{new},m+1}$ generated by S, it also will perform the similar check to guarantee the continuity and freshness of S’ $\mathrm{TID}$. After a successful verification, Cloud will make a signature on the CC$_{s-\mathrm{new},m+1}$ and generate CC$_{S-Cl,m+1}$, which is forwarded to C. C will verify the validity of the signatures in the received certificate and temporarily stores it. At this point, the first round verification process is completed.

• 3. The second round of the validation process

After the first round verification, through a secure channel, C sends its old certificate list CC$_{C-\mathrm{old}}$ to Cloud that forwards this list to S by means of the secure channel with S. Upon receiving the message, S will first verify the continuity of the certificates in the list, by checking the $\mathrm{TID}s$. Then S will verify the integrity of the certificates by checking whether the $\mathrm{TID}$ of the last certificate in the list is n or not. If both the verifications are successful, S will verify the total number of certificates in the list by one-time batch verification. If successful, S will count all the role flags in the certificate list, and calculate the C’s reputation $D_c$ by means of Eq. (5):

$$\begin{aligned} { D}_{C} = \frac{\mathrm{The\ times\ of\ service\ provision}}{\mathrm{The\ times\ of\ service\ request}}= \frac{\sum \mathrm{RF} = 0}{\sum \mathrm{RF} = 1}\ge \lambda \end{aligned}$$

(5)

In this equation, $\lambda$ is a probability threshold based on the fuzzy logic, which is used to evaluate a user’s reputation. Notice that the certificate list is empty when a node first implements this protocol, we modify the above formula inspired by Bayesian theory and the final one is as follows:

$$\begin{aligned} { D}_{C}=\frac{1+\sum (\mathrm{RF}=0)}{2+\sum (\mathrm{RF}=1)}\ge \lambda \end{aligned}$$

(6)

When C’s reputation $D_C$ satisfies the above relation, all the verifications pass and S will send a verification success message to C through Cloud. At this point, the second round verification process is completed.

• 4. Transaction process

When C receives the verification success message, two rounds of verification are complete and the transaction will begin.

After sending the verification success message to C, S makes its signature on CC$_{C-Cl,n+1}$ and generates C’s complete certificate CC$_{c,n+1}$ in this transaction. Then S sends it to Cloud which will verify whether the $\mathrm{TID}$ is n+1. If successful, Cloud will verify the certificate and store it temporarily. When C receives the successful verification message from S, it will also construct the complete credit certificate CC$_{s,m+1}$, and sends it to Cloud, which also needs to verify the freshness of the $\mathrm{TID}$ and the validity of the certificate. If the verification is successful, Cloud will send a positive acknowledgement message to S. Now, Cloud holds two complete certificate credits of C and S.

Upon receiving the successful verification message from C, S encrypts its position $P_S$ using C’s public key $\mathrm{PK}_C$, and makes a signature on the encrypted position as well as on the $\mathrm{TIDs}$ of two sides in this transaction. Then, S sends this message to Cloud, which forwards the message to C. C will add S into the anonymity set, and construct the anonymity area based on the positions that other members provide.

Meanwhile, Cloud adds 1 to S and C’s respective $\mathrm{TIDs}$, and sends the credit certificates temporarily stored to the other sides. Those certificates are generated by C and S themselves, and are signed by Cloud and the other side, therefore, they are legal and represent their behaviors in the transaction. The certificates are added into their respective certificate lists.

• 5. The case when a transaction fails

Since the protocol consists of multiple verification processes, any failure in those processes will result in the termination of the scheme. C and S have generated new credit certificates before the transaction and they will become incomplete ones when the protocol ends abnormally. Therefore, Cloud will not update the $\mathrm{TIDs}$ until S provides its position to C. Once the transaction fails, C, S and Cloud will delete those incomplete certificates and the $\mathrm{TIDs}$ will not be updated.

5 Security analysis

This section will analyze the security of the proposed scheme and give some consideration for the implementation.

Let us recall our assumptions: C and S are not trusted and they may collude, whereas Cloud is semi-trusted. Therefore, we will give the security analysis from the following aspects. The former two attacks come from internal attackers C and S. The third one is from an external attacker, and the fourth one is the free-riding behavior introduced by the incentive mechanism.

• 1. Three kinds of attacks from C or S

  • (1). C enjoyed too many assistance provided by other nodes, so that its credit value $D_c$ is below the threshold and cannot get more help. On the other hand, in the earlier time it provided a great deal of assistance to other nodes. Therefore, in the second stage, instead of sending the entire certificate list to S, C just sends a part of continuous certificates in the front of the list, which can satisfy $D_C\ge \lambda$. Thus, S will be tricked to provide assistance to C. However, in our scheme, S is required to check the $\mathrm{TID}$ of the last certificate in C’s certificate list. If the $\mathrm{TID}$ is not n (this value has been obtained in the first round of verification), S will not continue the transaction. In such a method, the attack can be prevented.

  • (2). Regarding C, a more smart attack is to forge a new transaction number $\mathrm{TID}'< n+1$ in the first round of verification and let S believe that this is the latest transaction number. Then, in the second round of verification, C just needs to send the certificates with $\mathrm{TID}$ between 1 and $\mathrm{TID}'-1$. Since this sublist meets the requirement $D_c\ge \lambda$, thus, C can get the assistance from S. The specific attack process is as follows. In the first round of verification, C replays the certificates signed by Cloud which transaction number satisfies $\mathrm{TID}' < n+1$. In such a way, the receiver S will regard $\mathrm{TID}'$ as C’s latest transaction number. Our scheme has two ways to deal with this attack: (a) the established secure channel between Cloud and S can prevent this replay attack; (b) this attack will result that in the fourth stage the transaction number in C’s complete credit is not $n+1$, and then Cloud will not accept this credit certificate.

  • (3). In the early stage, if C requested too many assistance, it attempts to delete the certificates with $RF=1$ from its list. In this way, it can get the assistance from S. However, in the second round of verification, S will check the continuity of the certificate list, thus guaranteeing that some certificates will not be deleted.

• 2. The collusion attack between C and S

  • (1). When C and S collude through the normal protocol process, they attempt to cooperate each other to generate certificates with $RF=0$ to achieve mutual benefits, but this attack is impossible in our scheme. Due to the existence of the Cloud, in the first round verification process, the role flag of C has to be set as 1. That is, if S gets an assistant-provision certificate, then C has to generate an assistant-enjoyment certificate. Again, the continuity of the $\mathrm{TID}$ can ensure that the assistant-enjoyment certificate cannot be modified or deleted. In this case, C and S cannot both benefit from the collusion attack. Therefore, the scheme can effectively prevent the collusion attack between nodes.

  • (2). In addition, C and S also may attempt to launch the collusion attack through the off-line fashion. More precisely, they will delete the unfavorable certificates ($RF=1$) in their respective lists and and cooperate with each other to forge favorable certificates ($RF=0$) for both sides. Notice that in the forged certificates the $\mathrm{TIDs}$ are same as the ones in the deleted certificates. In our scheme, the credit certificate not only needs the signatures of S and C, but it also needs Cloud’s signature. Finally, it is assumed that Cloud does not collude with C or S, therefore, the off-line collusion attack cannot succeed.

• 3. Replay attack

  The attacker attempts to replay protocol messages to impersonate C or S. If the attacker impersonates C, he can enjoy the assistance provided by other nodes without paying any price. If the attacker impersonates S, the latest $\mathrm{TID}$ of S stored in Cloud will be increased. Then, when the real S runs the protocol, it cannot pass the $\mathrm{TID's}$ freshness check performed by Cloud, so that it cannot enjoy the K-anonymity service any longer.

  Our scheme provides two ways to deal with the replay attack: (1) the secure channels between C and Cloud, S and Cloud can avoid the replay; (2) the latest $\mathrm{TIDs}$ stored in Cloud for each node also can avoid this attack.

• 4. Free-riding behavior

  Free-riding behavior denotes that a node enjoys other node’s services without paying any prices, which is an important issue to be solved in the incentives mechanism. Our scheme prevents this behavior through refusing to provide assistance to the node whose $D_c$ is below the threshold. Furthermore, to prevent a malicious requester C from refusing to sign the certificate of S after getting the latter’s assistance, we adopt the approach with the guaranteed transaction. That is, at the beginning of the fourth stage, C and S are required to sign the other side’s certificates to generate a final complete certificate for this transaction and deliver them to Cloud for temporary storage. Until Cloud verifies the validity of the certificates and S provides C its position, Cloud will forward the stored certificates to the other sides. In such a way, the free-riding behavior can be effectively avoided.

Meanwhile, we also compare the proposed scheme with the one in Yang et al. (2013), which is currently the first and only scheme that introduces auction-based incentive mechanism to LBS privacy protection. Our scheme employs the credit-based incentive mechanism and has an important advantage with respect to (Yang et al. 2013) in the following two aspects:

• 1. Yang et al. (2013) is based on the auction, and the auctioneer can get a user’s privacy degree and bid information. Consequently, a trusted server is needed to behave as the auctioneer, which will introduce a great deal of extra overhead. Instead, in our scheme, Cloud just can get S and C’s identities in the first round of verification. We remark that since in the fourth stage the S’ position is encrypted using C’s public key, Cloud cannot get C’s position. Therefore, in the whole scheme, Cloud can just get which nodes performed the transaction. Consequently, Cloud is just needed to be semi-trusted. The off-the-shelf cloud service can realize the expected function, which is very easy to implement. Meanwhile, it can also avoid the case that the users’ privacy information is revealed because of the trusted third server is broken.

• 2. The auction-based incentive mechanism in Yang et al. (2013), essentially belongs to the direct reciprocity incentives, nodes’ behaviors just affect the current transaction and they do not have any impact on the subsequent transactions. Therefore, it is only suitable for the scenario where a single transaction lasts long and there are relatively fixed participants. Instead, in the LBS, nodes move frequently, there are no fixed nodes and the transactions always do not last long. Moreover, in Yang et al. 2013 the auction is based on the nodes’ energy consumption and traffic. While, for different mobile devices, their performance vary greatly. Therefore, the devices with low capacity are always disadvantaged and cannot get a fair opportunity. Consequently, this mechanism is not suitable for the LBS privacy protection. Our proposed method is based on the credit-incentive mechanism. In each transaction, each participant generates a credit certificate which has nothing to do with the devices. The certificates generated in each transaction are stored locally and continue to be accumulated. Each transaction has direct impact on the subsequent ones, which promotes the nodes to actively participate in the transactions, so as to achieve a long-term incentive effect.

6 Consideration for the implementation aspect

• 1. The credit certificates stored locally Since in the proposed scheme the credit certificates are maintained and updated by the nodes themselves, the maintenance of the certificates is an important issue. A circular queue is employed to store the credit certificate list. The maximum length of the list is N. When the queue is full, according to the characteristics of the circular queue, i.e., FIFO, the certificates that are first stored in the queue are deleted first. That is, instead of considering the whole historical credit, we just consider the node’s credit in the recent N transactions.

  In addition, to prevent the case that the certificate list cannot be accessed because there is something wrong with the devices, users can store the certificate list in the cloud. However, this is beyond the scope of this paper.

• 2. Batch verification of the old certificate list

  To reduce the time and energy consumption for the verification of C’s old certificates, the batch signature verification technology, i.e. EdDSA, is employed in our scheme. The EdDSA algorithm is proposed in Golle et al. (2001), which is a special elliptic curve digital signature algorithm (ECDSA). This algorithm can verify not only a single certificate, but also multiple certificates in a batch verification method, to speed up the verification of the certificate list. The time consumption for the batch verification has the same magnitude order as that for a single signature. Again, EdDSA is secure and its security strength with 128 bit keys is approximately equal to the one of RSA with 3000 bit keys. Finally, EdDSA has been proved to be efficient (Daniel et al. 2012).

  The algorithm selects the elliptic curve $ed - 25519$ where B is the base point of the elliptic curve, and the little-endian of the data coding method is employed to compress data. Node’s private key is a string k which is b-bit in length, and the public key A (the compressed expression of A which is generated by the private key k and base point B) is computed by Eq. (7):

$$\begin{aligned} H(k)=(h_0,h_1,\ldots ,h_{2b-1}) \end{aligned}$$

(7)

$$\begin{aligned} a=2^{b-2} + \sum \limits _{3\leqslant i\leqslant b-3}2^{i} h_i \in \left\{ 2^{b-2},2^{b-2}+8,\ldots ,2^{b-1}-8\right\} \end{aligned}$$

(8)

$$\begin{aligned} A=aB \end{aligned}$$

(9)

The message to be signed is M, and the signature calculation process is described by the following equations:

$$\begin{aligned} r=H(h_0,h_1,\ldots ,h_{2b-1},M) \end{aligned}$$

(10)

$$\begin{aligned} R=rB \end{aligned}$$

(11)

$$\begin{aligned} S=(r+H(\underline{R},\underline{A},M)\,a\,)~\mathrm {mod}~l \end{aligned}$$

(12)

$$\begin{aligned} sig=(\underline{R},\underline{S}) \end{aligned}$$

(13)

When C or S receives a new certificate from the other side, they just need to validate a single certificate, by verifying Eq. (14):

$$\begin{aligned} R=SB-H(\underline{R},\underline{A},M)A \end{aligned}$$

(14)

When S receives the old certificate list from C, it will validate the all the old certificates using the batch verification described by the following equations:

$$\begin{aligned} H_i=H(\underline{R_i},\underline{A_i},M_i) \end{aligned}$$

(15)

$$\begin{aligned} \left( -\sum \limits _{i}{}{z_iS_i~\mathrm {mod}~l}\right) B+\sum \limits _{i}{}{z_i\underline{R_i}} + \sum \limits _{i}{}{(z_iH_i~\mathrm {mod}~l)\underline{A_i}}=0 \end{aligned}$$

(16)

In the above formula, $z_i$ is a random value.

7 Experiment and performance analysis

The topology of the testbed built for the experiment is shown in Fig. 3. C, S and Cloud, all use HP Desktops (3.00GHz Core 2 Duo CPU and 2GB DDR3-1600 RAM, TP-LINK TL-WN822N 802.11N wireless card, Microsoft Windows7 32-bit operating system). C and S are connected to the AP through a wireless channel, and Cloud connects to the AP through a cable connection. The proof of concept of our scheme is written by C/C++ language.

Fig. 3

The topology

In the experiments, the multi-thread programming is adopted to virtualize $K-1$ S nodes.

The signature algorithm adopted is Ed25519-SHA-512, and the parameters are set as follows: $b = 256$, H is the hash algorithm SHA-512, q is a prime of $2^{255}-19$, $F_q$ is {0,1, ..., 2255-20} of little-endian coding with 255 bits in length, d = $-$121,665/121,666 $\in F_q$, the prime number $\ell$(Bernstein and Curve 2006) = $2^{252}$+2,774,231,777,737,235 3,535,851,937,790,883,648,493, $B=(x,4/5)\in E$, where $x> 0$. The elliptic curve equation in the field $F_q$ is $v^2=u^3+486,662u^2+u$.

7.1 The time needed to establish the anonymous set

In the experiment, N, the number of the old certificates stored locally, is set as 20. Then, we set the size of anonymous set K as different values, to respectively test the time for C to construct the corresponding anonymous sets. The value K is set as 5, 10, 20, 30 and 40 respectively, and for each K value the experiments are performed 10 times and the results are shown in Fig. 4.

Fig. 4

Time to form the anonymous area

The average time to form the anonymous area for different K values in Fig. 4 is shown in Table 2. From which it can be seen that, with the growth of K, the time to form the K-anonymous area increases slowly.

Table 2 The average time to form the anonymous area for different K values

The size of anonymous set K is fixed and we adjust the value of N which is the size of the old certificates stored locally. The average time to form anonymous areas is shown in Fig. 5. For each N value, the experiments are performed 10 times and we get the average value. It can be seen that, with the growth of N, the increase of the time to form the anonymous area is negligible. From the results, we can see that the value of N almost has no influence on the time to establish the anonymity area, which indicates that the batch verification is efficient.

Fig. 5

Relationship between time and N

Table 3 Calculation amount of C and S

7.2 The computational amount for C and S

Because Cloud is powerful in the computational capacity, we do not care about its computational amount.

In the first verification round of the scheme, C has to make one signature and one batch verification, required to verify the signatures of Cloud and S. In Step 4 transaction process, C has to make one signature to generate the final certificate for S, one signature verification to verify the signature of S for the position $P_S$ and one decryption to get $P_S$.

In the first verification, S has to make one signature and one batch verification to verify the signature of C and Cloud. In the second round of the verification, S needs to make one batch verification. In the transaction process, S has to make one signature to generate the final certificate for C, and one public encryption to encrypt its position.

The computational amount for C and S in the scheme is shown in Table 3.

If the public key operation is performed on the elliptic curve, its computational amount and energy consumption is acceptable.

7.3 The traffic analysis for the construction of the anonymity area

The traffic consumed by C to form the anonymous set is shown in Fig. 6. It can be seen that, when the value of K is fixed, the traffic of C monotonically increases with the value of N. And when the value of N is fixed, the traffic of C also monotonically increases with the value of K.

The traffic that the node S generates to construct the anonymous set is shown in Fig. 7. It can be seen that, when the value of K is fixed, the traffic of S monotonically increases with the increases of N. Meanwhile, when the value of N is fixed, the traffic of S is almost constant when the value of K increases. That is, the traffic of S is independent on the anonymous area size K.

The above analysis shows that the number of locally stored certificate N has impact on the traffic to construct the K-anonymous area. More precisely, with the increase of the value of N, the traffic generated by C and S will grow, while a node’s historical credit is reflected better. In addition, Fig. 5 indicates that the size of N has almost no influence on the time to construct the anonymous set.

7.4 An example

As an example, we first set K as 40, which is a rather big value for the anonymity set. That is, the user has a comparatively high requirement for the privacy. Then, the time to establish the anonymity set is 4.92 s. Meanwhile, because a bigger value of N can reflect a node’s historical credit more completely, therefore, the value of N is set as 100. Again, the traffic generated by C and S respectively is 55.48 and 21.86 kb, which is acceptable. In addition, for C and S, the space needed for the storage of old certificates is 19.76 kb. Compared to the popular Android APPs, which mostly needs storage space in the magnitude of megabytes, the storage space required by our scheme is very small. The related data in the above example is show in Table 4.

The above example demonstrates that even if a user has a comparatively high requirement for the size of the anonymity set and the number of the old certificates stored locally is rather big, the time to form the anonymity set, the traffic generated and the storage space required is acceptable. Consequently, the proposed scheme is feasible.

Fig. 6

Relationship between C’s traffic and K, N

Fig. 7

Relationship between S’ traffic and K, N

Table 4 Related Parameters when $K=$ 40, $N =$ 100

8 Conclusions

In this paper, the incentive mechanism based on the credit is first introduced into the LBS privacy protection for the P2P networks. By refusing to provide assistance to users with a low reputation, users are promoted to actively participate in the construction of K-anonymity set, thereby achieving the incentive goal. This increases the feasibility of distributed K-anonymity schemes, which has been widely investigated in LBS privacy protection. In order to evaluate a user’s reputation, a probability threshold is introduced based on the fuzzy logic.

Security analysis shows that the proposed scheme can defeat various insider attacks, collusion attacks, replay attacks, and free-riding behavior in the incentive mechanism. Compared with the scheme in Yang et al. (2013), the proposed scheme considers the user’s history behaviors, therefore, the persistent incentive effect is more salient. Furthermore, it does not require a trusted third party, avoiding the security issues resulting from its breach. Consequently, it is a secure incentive scheme.

Finally, a WiFi testbed is established where the scheme is implemented. Extensive experiments indicate that the time needed to construct the anonymity set is short and it increases slowly with the growth of the set size. Therefore, the proposed scheme is a secure and practical incentive scheme for the distributed K-anonymity.