1 Introduction

The increasing availability of sensors on today’s smart phones has already opened up new possibilities for gathering sensed information from our environment. Mobile crowd sensing (MCS) [1, 2] refers to the wide variety of sensing models in which individuals with sensing and computing devices are able to collect and contribute valuable data for third parties. MCS can be deployed on many field applications ,such as cloud computing applications [14, 18, 21], smart grids applications [6, 10–13] and so on. More details, MCS applications can be used to enable a broad spectrum of applications, ranging from monitoring the air pollution condition [3] or location based services to monitoring traffic conditions [4, 5] or social network applications [7, 15]. Figure 1 shows the typical fundamental structure of MCS. The participants use a sensor on mobile to obtain the data which is required about a subject of interest, and upload these data to a tasking entity such as a cloud service, where these data are aggregated, processed and remain available for third parties(e.g., traffic monitoring application or environmental monitoring department) to query and select data of interest. For example, in vehicular networks [9, 16], the traffic monitoring applications, sensors carried by drivers can collect the information of the traffic condition in real time and real location, such as the traffic flow, traffic jam information and so on, and share these information to the tasking entity(e.g., cloud service), which may be used by third parties (e.g., other drivers) who can select a best transportation route to avoid the traffic jam. Another example of its application is that commercial organizations may be very interested in collecting mobile sensing data to learn more about customer behavior, which demonstrates how useful and beneficial MCS is to our lives. Without doubt, MCS makes our life more convenient and wonderful.

Fig. 1
figure 1

A typical structure of crowd-sensing application

Full size image

Despite the past nontrivial effort, MCS is still in its infancy, attracting increasing research attention, especially for the privacy protection of users, which is challenging in MCS due to its unique characteristic. For instance, in the traffic monitoring application, as the participants issue the traffic condition and bring much benefit for the third parties, their location and time information will be exposed to the third parties simultaneously. Thus, it is important to design a method to ensure the participants can anonymously access and share the information, which can protect their privacy effectively. Namely, the tasking entity and the third parties users only need to know the traffic conditions, but not know other private information such as participants’ IP addresses and identities, etc. On the other hand, participants are not always trustworthy since they may submit false data unscrupulously to earn benefits for themselves. Thus, we need to prevent the misbehavior of participants with respect to the upload of data to tasking entity. Therefore, the proposed scheme can not only protect participants’ privacy, but also prevent malicious users from uploading data.

By carefully exploring the intrinsic characteristics of MCS and considering the Quality-of-Experience (QoE) [8] and examining the existing anonymous authentication schemes, we present a Practical Blacklist-based Anonymous Authentication scheme for Mobile Crowd-sensing. Specially, the main contributions of this paper can be summarized as follows:

  • Practical reputation scores. We measure the participant’s access authority by his behavior scores which is scored by application provider. Application provider can score each user with a positive or negative score with a category identifier.

  • Blacklisting malicious users. We propose a technique that can prevent the malicious users’ misbehavior. In our scheme, the application provider provides a series of policies that participant’s reputation scores must satisfy. Otherwise, the participant will be added in the blacklist, therefore the participant cannot enjoy the anonymous environment of MCS. In particular, our scheme can add misbehaved users to a blacklist using their pseudonyms instead of their real identity, thereby preventing the potential privacy leakage.

  • Efficiency. Our scheme takes full consideration of the computational ability of mobile devices. The proposed scheme is mainly based on the symmetric-key encryption to achieve anonymous authentication instead of the cost-heavy public-key encryption or pairing. Thus, the proposed scheme is efficient and particularly suitable for resource-constrained mobile clients of MCS.

The remainder of this paper is organized as follows. In Section 2, the system model and security requirements are formalized. We present notations and cryptographic primitives in Section 3. In Section 4, we propose our scheme. Followed by the security analysis and performance evaluation of our scheme in Section 5 and Section 6, respectively. We present the related work in Section 7. Finally, we conclude this paper in Section 8.

2 System model and security requirements

2.1 System model

As shown in Fig. 2, there are four types of entities involved in our scheme: participant, pseudonym manager(PM for short), application provider(AP for short) and network manager(NM for short).

  • Participant: Participant is the entity that measures and shares required data about a subject of interest to the application provider by using sensors on everyday devices, such as smart phones, personal digital assistant(PDA). However, not all participants are always honest since some participants maybe misbehave.

  • Pseudonym Manager(PM): PM is in charge of mapping the participant’s resources id(e.g., IP address, MAC address), to the pseudonyms. PM is the first entity that the participant must contact, which determines whether the participant is permitted to register or not. As a result, PM’s duties are limited to determining the right of registration and mapping IP address to pseudonym.

  • Application Provider(AP): AP not only provides the services to the user but also manages the reputation scores of a participant, including scoring grades, updating scores and modifying scores. In addtion, AP maintains a blacklist which is used to determine participant’s right of enjoying the anonymous environment of MCS. AP lays down the policies that each participant must satisfy, otherwise, the participant cannot enjoy the anonymous environment.

  • Network Manager(NM): NM is the control center of the system. NM initializes the system parameters, such as secret keys and secure hash functions, and issues them to other entities. Moreover, NM is in charge of maintaining and computing the participant’s current scores and generating the participant’s credentials in order to authenticate with AP. As we will explain, NM only knows which AP that participant wants to contact, the other information, such as the participant’s IP address, is kept unknown.

Fig. 2
figure 2

System model for anonymous authentication scheme

Full size image

2.2 Security requirements

We present informal definitions of the desired security properties. The security requirements in our scheme should cover these four aspects.

  • Anonymity: Adversary can get only a train of pseudonyms of participants instead of the real identity based on the existing communication.

  • Blacklistability: Only a participant who is not in the black list can obtain the anonymous service. In other words, a participant cannot obtain the service if he has been put in the backlist.

  • Nonrepudiation: The property of nonreputation is a fundamental requirement for our scheme. Namely, a participant cannot deny that he has accessed the service provided by AP.

  • Unlinkability: All of the messages generated by a participant should not leak any information to an adversary by allowing the adversary to trace them.

3 Preliminaries

3.1 Notation

For easier illustration, Table 1 lists some important notations which will be given further explanation where they occur for the first time.

Table 1 Notation
Full size table

4 Proposed scheme

In this section, we propose our scheme, which mainly consists of the following five phases: System Initialization, Participant Registration, Authentication, Update scores and Modify scores.

4.1 System initialization

During system setup, NM interacts with other entities. First, NM generates a number of private keys for the system. The private key m a c K e y N P ∈ {0, 1}m, which is used to generate the pseudonym for PM and verify the integrity of pseudonym for NM, and then NM issues it to PM through a secure communication channel. The key K e y N A ∈ {0, 1}m shared with AP is used by NM and AP to exchange information secretly, and send them to AP over a secure channel. In addition, NM generates the private key s e e d K e y N ∈ {0, 1}m ,which is used to generate the seed, the private key e n c K e y ∈ {0, 1}m is used to generate the SCUP. At the same time, NM applies a public key pair (P r i K e y N ,P u b K e y N ), where P r i K e y N ∈ {0, 1}m is the private key, and the P u b K e y N is the corresponding public key. NM also picks a number of secure hash functions. The secure hash function \(\mathcal {H}_{0}:\{0,1\}^{\ast } \times {\{0,1\}^{m}} \rightarrow {\{0,1\}}^{m}\) to generate the pseudonym for PM, and the secure hash function \(\mathcal {H}_{1}:\{0,1\}^{m} \times {\{0,1\}^{\ast }}\times {\mathbb {Z}_{q}}^{\ast } \times {\{0,1\}^{m}} \rightarrow {\{0,1\}}^{m}\) to generate the s e e d 0. Finally, NM publishes these hash functions \(\mathcal {H}_{0}\) and \(\mathcal {H}_{1}\).

4.2 Participant registration

In our scheme, a participant must use a ticket which is requested from NM to authenticate. As illustrated in Fig. 3, the transaction is divided into linkability windows of duration w, each of which is split into m transaction identifiers. Particularly, a participant must register once in each linkability window, namely, after accessing to AP m times, the participant must register again.

Fig. 3
figure 3

The life cycle of anonymous authentication

Full size image

4.2.1 Create the pseudonym

A participant with identity uid must apply for a pseudonym ctpd from PM firstly. A pseudonym ctpd consists of nym and mac: nym is a hash mapping of the participant’s identity (e.g., IP address or other resources), the linkability window W c r t for which the pseudonym is valid, mac is used to verify the integrity of pseudonym by NM. We suppose PM owns a long-term secret p m K e y p ∈ {0, 1}m, which is used to generate the nym. Therefore, after receiving uid from the participant, PM calculates the participant’s ctpd as below algorithm.

$$\begin{array}{@{}rcl@{}} nym&=&\mathcal{H}_{0}(uid||W_{crt}, pmKey_{p})\\ mac&=&\mathcal{H}_{0}(nym||W_{crt}, macKey_{NP})\\ ctpd&=&(nym, mac) \end{array} $$
(1)

where the m a c K e y N P is the secret key shared with PM and NM. After successfully generating ctpd, PM sends it to participant.

4.2.2 Verify the pseudonym

Participant must register to NM to get the ticket to authenticate. Thus, the participant sends the ctpd and sid to the NM for registering, where sid is the identity of AP which participant wants to access. After receiving ctpd, NM firstly checks its freshness and integrity. Thus, NM reads the current linkability window as W c r t , which guarantees the freshness of pseudonym, and then extracts the nym and mac from the ctpd to check the integrity of pseudonym is as following.

$$ mac=\mathcal{H}_{0}(nym||W_{crt},macKey_{NP}) $$
(2)

NM accepts the pseudonym if and only if the above formula is tenable, otherwise, terminates the scheme with failure.

4.2.3 Create the participant’s score list and credential

In order to save a participant’s reputation scores, NM maintains a score list \(\mathcal {L}\) for the participant. The list \(\mathcal {L}\) can correctly record different participants scores.

As shown in Table 2, the score queue \(\mathcal {L}\) consists of three parts: the unique identifier, the previous score and the recent K transactions.

  • The Unique Identifier: The first value(P s d m 0) is the unique identifier to distinguish various participants. For the same participant, the P s d m 0 is different if the AP which the participant wants to access is different, since P s d m 0 is a mapping value of sever identity sid. Using the unique identifier P s d m 0, NM can correctly compute and update the participant’s scores. The more explanation of P s d m 0 as following.

  • The Previous Score: The middle L values represent a participant’s current scores of L categories. In our scheme, AP scores a participant’s behavior from different perspectives. In our scheme, each transaction identifier is associated with L scores.

  • The Recent K Transactions: In order to prevent NM from updating the participant score repeatedly, the recent K transaction identifiers are reserved.

The score list L is initialized to null, that is, besides the unique identifier, the previous scores and the recent K transactions are all initialized by null.

Table 2 Scores list data structure
Full size table

Particularly, the participant must provide a valid ticket which is acquired as part of a credential from the NM to AP for authentication at each time. The pseudonym P s d m in the tickets which serves as an identifier for a particular time period, and the P s d m is evaluated from the seeds.

Seed as a parameter evolves throughout a linkability window using a seed-evolution function \(\mathcal {F}\), the seed for the next transaction identifier s e e d n e x t is computed from the seed for the current linkable window s e e d c u r , that is:

$$ seed_{next}=\mathcal{F}(seed_{cur}) $$
(3)

The first seed (s e e d 0) is generated by hashing a participant’s pseudonym ctpd, the identity sid of the server, the linkability window W c r t for which the seed is valid, and the secret key s e e d K e y N of NM. As a consequence, a seed is useful just for a particular AP to access a particular participant during a particular linkability window.

$$ seed_{0}=\mathcal{H}_{1}(ctpd, sid, W_{crt}, seedKey_{N}) $$
(4)

P s d m as an identifier is used to authenticate with AP. Just like the generation of a seed, the Psdm(P s d m t ) for a certain linkable window is generated from the corresponding seed(s e e d t ) by applying the psdm-evaluation function \(\mathcal {G}\) as following:

$$ Psdm_{t} =\mathcal{G}(seed_{t}) $$
(5)

However, NM calculates the first corresponding P s d m 0 by using the psdm-evolution function g as: P s d m 0 = g(s e e d 0). Thus, every P s d m is only associated with one seed. Obviously, without a seed, adversary can not generate the the sequence of P s d m.

A credential must be provided by a participant. Particularly, a ticket is only used once for a particular linkability window. NM reads the current linkable window as w, and the computation of tickets and a credential for a participant is as algorithm-1: where the SCUP is the encrypted data. Especially, SCUP contains the first P s d m(P s d m 0), with which NM can easily update the scores or add a misbehaved participant to the blacklist. Particularly, the s c o r e = S 1∥S 2∥⋯∥S L , where S i represents the ith score. In addition, each ticket contains two parts: CT and TV. Particularly, TV is the encrypted data of CT, which not only protects the privacy of information, but can also verify the integrity of the P s d m ticket for AP. After successfully computing the C r e d, NM signs it by executing the encrypt function E n c to ensure the security of the data.

$$ Cred_{S}ig = Enc(Cred, PriKey_{N}) $$
(6)

where P r i K e y N is NM’s secret private key especially. Finally, NM issues <C r e d, C r e d S i g > to the participant, where the C r e d S i g is the signature of C r e d. Figure 4 describes the message flow of the creating and verifying the participant’s credential phase.

figure f
Fig. 4
figure 4

The process of creating and verifying credential

Full size image

From above, we can easily see that as long as the PM and NM do not collude, the system cannot identify which participant is connecting to which server; the NM only knows the pseudonym-server pair and the PM only knows the user identity-pseudonym pairs.

4.3 Authentication

A participant must provide a valid ticket, which is acquired as part of a credential from the NM to authenticate. Firstly, the participant must check whether it is in the blacklist or not. If a participant finds that it is in the blacklist unfortunately, as an honest participant, it terminates the scheme immediately. Otherwise, the participant sends its tickets to AP, and AP passes the participant’s authentication if the participant’s reputation scores satisfy the policy. We should note that the whole procedure take place under the anonymous condition, namely AP knows nothing but a series of scores.

4.3.1 Check whether blacklisted

Participant must verify the signs firstly to guarantee the integrity of C r e d S i g . The process of checking is as following:

$$ Cred = Dec(Cred_{S}ig, PubKey_{N}) $$
(7)

where the P u b K e y N is the public key of NM. If the above equation is established, participant then checks whether it is in the blacklist via comparing with the P s d m value in the blacklist or not. The blacklist is composed of a series of P s d m 0, the current linkability window W c r t and the current transaction identifier. Especially, the current linkability window and the current transaction identifier guarantee the freshness of the blacklist. If the participant’s P s d m 0 is in the blacklist, then the authentication procedure is terminated and is regarded as a failure. Otherwise, the participant must extract the tickets from the C r e d and sends it to AP.

4.3.2 Check whether the policy is satisfied

When the AP receives the tickets, it checks the validity of tickets as following.

  • The validity of tickets: AP extracts the TV and CT from the tickets, performs the following operations to check the integrity of tickets:

    $$ CT = Decrypt(TV, Key_{NA}) $$
    (8)

  • The freshness of tickets: AP reads the current linkability as W n o w , and compares it with the w in CT. If W n o w equals to w, it proves that the tickets are fresh.

AP rejects the request if the ticket is not valid or fresh. Otherwise, AP checks the participant’s score to see whether it satisfies the policy, which is a boolean combination of scores category-threshold and is stored in AP database. Particularly, AP formulates a policy ply which is made of several different sub-policies p l y i , and a sub-policy consists of boolean combinations of L scores, i.e.,

$$\begin{array}{@{}rcl@{}}ply &=& ply_{1}\vee ply_{2}\vee ply_{3}\vee {\cdots} \vee ply_{n}\\ ply_{i} &=&S_{p_{1}} \| S_{p_{2}}\| {\cdots} \|S_{p_{L}} \end{array} $$
(9)

Every participant must satisfy one of sub-policies. Therefore, AP extracts scores from the tickets, and proves that the participant’s every category score is less than one of corresponding sub-policy scores. That means, there exists an integer k: p l y k = S p 1∥S p 2∥⋯∥S p L and for each value i for i=1 to L satisfies

$$ S_{i}>S_{p_{i}}\ \ \ \ 1 \leq i \leq L $$
(10)

Where S i presents the participant’s current ith score. If the participant’s scores satisfy the policy, AP provides the service to the participant. From above, we can easily conclude that AP does not know the participant’s real identity.

4.3.3 Add participant to the blacklist

Sometimes, the participant’s scores do not satisfy any policy unfortunately, thus, AP will add the participant to the blacklist and not provide it anonymous service anymore. However, AP does not know any of the participant’s information due to the anonymity property of the authentication procedure. Therefore, AP applies to NM for the participant’s first pseudonym(P s d m 0) to add it to blacklist. AP generates a boolean value black and sets it true, which represents that participant’s score doesn’t satisfy the policy. AP sends the TB which is the encrypted data of ticket and boolean value black to NM as follows:

$$ TB=Encrypt(ticket||black,Key_{NA}) $$
(11)

where K e y N A is the secret key shared by NM and AP. As we know, only NM can decrypt TB, which guarantees the security of information. When receiving the “black” message, NM computes the P s d m 0 for AP. First of all, NM decrypts the data of TB and extracts the S C U P t to compute the P s d m 0 as follows:

$$\begin{array}{@{}rcl@{}} &&ticket||black=Decrypt(TB,Key_{NA})\\ &&Psdm_{0} =Decrypt(SCUP_{t},encKey) \end{array} $$
(12)

After computing P s d m 0 successfully, NM sends it to AP. For security, NM firstly encrypts it as follows:

$$ PB=Encrypt(Psdm_{0}||tickets,Key_{NA}) $$
(13)

When receiving the encrypted P s d m 0, AP decrypts it as P s d m 0||t i c k e t = D e c r y p t(P B, K e y N A ). And NM adds P s d m 0 to his black list. Thus, the malicious participant is added into the blacklist successfully. Figure 5 describes the message flow of the adding malicious users to the blacklist.

Fig. 5
figure 5

The process of adding malicious users to blacklist

Full size image

4.4 Update scores

AP can score any behavior of a participant. For any special transaction identifier, AP can give it a proper reasonable score. Let us say the score is: \(UPSCORE=S_{UP_{1}} \| S_{UP_{2}} \| {\cdots } \| S_{UP_{L}}\) where the \(S_{UP_{i}}\) represents the ith category score. AP sends the scores UPSCORE, transaction identifier t i and P s d m t to NM for updating. AP extracts the P s d m t and the transaction identifier t i , and encrypts it as follows:

$$\begin{array}{@{}rcl@{}} &&US=Psdm_{t}\|t_{i}\|UPSCORE\\ &&UPSC=Encrypt(US,Key_{NA}) \end{array} $$
(14)

where the UPSCORE are scores of participants scored by AP. Only NM can decrypt UPSC since only NM knows the secret key K e y N A .

NM updates the scores for the participant. When receiving the UPSC, NM checks its validation as shown bellow:

$$ US=Decrypt(UPSC,Key_{NA}) $$
(15)

Assume the above equation is tenable, then, NM extracts the t i from the US, and checks the value via comparing with the recent K transaction identifier. If the t i is in the recent K transactions, NM extracts the score as bellow.

$$ S_{UP_{1}} \| S_{UP_{2}} \| {\cdots} \| S_{UP_{L}}=UPSCORE $$
(16)

for i=1 to L,

$$ S_{i}=S_{i}+S_{UP_{i}} $$
(17)

After this computation, NM successfully updates the participant’s score in the score list \(\mathcal {L}\).

4.5 Modify scores

If at some later time, AP desires to upgrade a score for transaction identifier t. Let the original score be S 1, S 2, ⋯, S L , and the updated score be \(S_{1}^{\prime }\), \(S_{2}^{\prime }\), ⋯, \(S_{L}^{\prime }\), and the difference is d, that means the value \(d_{i}=S_{i}^{\prime }-S_{i}\). Therefore, AP just only sends the value d i to NM to upgrade the score. Let the L categories update score d = d 1∥d 2∥⋯∥d L . AP creates a boolean value MD, and sets it to true. AP encrypts the P s d m t and the value d and sends them to NM. Let M D S C = P s d m t ∥d∥M D, AP uses the shared key to encrypt it and sends to NM. That is

$$ EMSC=Encrypt(MDSC,Key_{NA}) $$
(18)

Upon receiving the EMSC, NM firstly checks if the message is valid by following operations.

$$ MDSC=Decrypt(EMSC,Key_{NA}) $$
(19)

NM extracts the boolean value MD and the difference of scores d. The boolean value MD represents that AP request to modify the previous scores. Therefore, NM adds the different score d i to the previous score S i as follows:

$$\begin{array}{@{}rcl@{}} &&For\ i=1 \ to\ L\\ &&S_{i}=S_{i}+d_{i} \end{array} $$
(20)

Thus, NM successfully upgrades the scores.

5 Security analysis

This section presents the security analysis of our authentication scheme. Our analysis will focus on how our scheme achieves anonymity, blacklistability, nonrepudiation and unlinkability.

5.1 Anonymity

Anonymity means that an adversary cannot obtain the real identity of any participant based on the existing communication. In the tickets presented by a participant, only P s d m t and S C U P t are functions of the user’s identity. However, since the adversary has not obtained any seed for the user, P s d m t is a series of pseudonyms, so adversary can get nothing from P s d m t . Moreover, because adversary does not know the NM secret key of encryption S C U P t and the security of AES, the adversary still cannot get any information of a participant. Furthermore, assume an adversary gets P s d m 0 that is issued to AP when a participant is blacklisted. However, the AP does not know the hash function and parameters of generating P s d m 0, so AP cannot get any information of the participant either. Thus, our proposed scheme can fully exert its ability of protecting a participant’s anonymity.

5.2 Blacklistability

It is easy to show that if each participant has been blacklisted in any previous transaction of the current linkability window, the participant cannot authenticate in the current transaction. AP adds P s d m 0 to the blacklist when a participant misbehaves. Next time, the participant terminates authentication when he finds his P s d m 0 is in the blacklist. At this point, as an honest participant, he will terminate authentication in that circumstance. However, in the real world, the participant may be not honest, so he connects to AP continually by using the tickets which are issued by NM. As long as NM and AP are honest, AP will terminate authentication as well. Namely, upon receiving the tickets, AP checks the participant’s scores to see whether or not it satisfies the policy, then terminates authentication if it fails. From the above argument we can draw a conclusion that our scheme meets blacklistablility perfectly.

5.3 Nonrepudiation

After a successful access, a participant cannot deny that he has accessed the service provided by AP. In our scheme, the tickets issued by NM blend participant and AP together. AP and NM use a secure hash function to map a unique source identity to a pseudonym. Each ticket evolves from the same s e e d 0 though NM issues many tickets for different transactions. Moreover, Since the security of hash function, every participant is associated with a unique s e e d 0, and every s e e d 0 is associated with a series of specific pseudonyms. As discussed above, we can conclude that there is no chance for a participant to deny that he has accessed the service.

5.4 Unlinkability

Unlinkability means that all sessions generated by a participant should not leak any information to the adversary. We assume the contrary that an adversary gets enough information so that he can distinguish all participants. From the adversary’s perspective, we can separate all of the tickets into two groups, one set of all the tickets come from the same participant, and the other one of all tickets come from different participants. In our scheme, every participant owns a unique s e e d 0, then generates a series of different tickets, thus the same participants has tickets that are different in different transactions. For different participants, because of the security of hash function, their tickets are different as well. Apparently, there isn’t significant evidence to prove that whether all tickets collected by the adversary come from one participant or not. We can easily conclude that our scheme meets unlinkability firmly.

We carefully select three existing schemes for comparative analysis and the results are summarized in Table 3. We discuss security properties of the above four aspects in these schemes respectively. The scheme in [27] only has the property nonrepudiation and unlinkability. In [19], only nonrepudiation property is satisfied. In LZCK [28], besides the property of blacklistability, the other properties are achieved. From Table 3, we can conclude that our new scheme achieves a higher security level with strict anonymity and other properties.

Table 3 Comparison of security properties among different schemes
Full size table

6 Performance evaluation

In this section, we evaluate the performance of the proposed scheme in terms of functionality and computation. In addition, we implement our scheme and gain the computation time of each phase. Especially, We compare our scheme with the LZCK [28] in the authentication phase.

6.1 Functionality

The basic aim of our proposed scheme is protecting privacy of the participant, as a result, we implemented the anonymous authentication technology. However, that technology brings a series of problems that the malicious participant abuse the environment of MCS. Therefore, we propose a practical and scalable scheme to support blacklist-based anonymous authentication. Especially, our scheme can limit the participant’s right to enjoy anonymous service. In our scheme, the participant’s right is measured by his own reputation scores which are scored with the participant’s previous behavior by AP with a positive or negative score on the score list. This method not only achieves limiting the participant’s right in the anonymous environment but also it is most practical and scalable for implementation on MCS.

6.2 Computation overhead

We have identified the major operations for each of the schemes as shown in Table 4. In particular, we list the run time of symmetric key cryptography and security hash function considering the limited computation ability for the participant of CMS(e.g. smartphones). The symbols T r s and T r v represent the time cost of RSA sign and verification, respectively. The symbols T s e and T h s represent respectively the time cost of the symmetric-key cryptography and cryptographic hash computation.

Table 4 Complexity analysis for every phase
Full size table

Particularly, we carefully select a scheme LZCK [28] and compare the computation of authentication. From the Table 5 we can see that the main computation cost in [28] is exponentiation in \({\mathbb {Z}_{q}}^{\ast }\), multiplication in \({\mathbb {G}_{1}}\) and pairing. And the symbols T e x , T m l and T p represent them respectively.

Table 5 Comparison of Computation overhead
Full size table

From Tables 4 and 5, we can easily draw a conclusion of our scheme’s computation complexity. In the participant Registration phase, total computation overhead of our scheme is 4T h s + 2T s e + T r s at PM and NM. However, the computation of LZCK [28] is 2T p + T r s . In the Authentication phase for our scheme at participant, the computation overhead is only T r v , and at AP is only T s e . However, In LZCK [28], the computation at the participant is 4T m l + T e x + 2T h s , and the computation at AP is T p + 2T m l + T e x + 2T h s . In Authentication phase, the computation overhead is 3T s e for both AP and NM respectively if the participant will be added in the blacklist. Otherwise, the computation overhead is only T s e . The other phases, including Update scores phase, Modify scores phase, the computation overhead is T s e for both NM and AP. The comparison of computation overhead is shown in Table 5. Consequently, our scheme is more efficient than LZCK [28].

To evaluate the computation overhead of the proposed schemes, we have implemented our scheme in C++. It uses the famous MIRACL library for the cryptographic operations. Especially, we use SHA-256 for the cryptographic hash functions, AES-256 in CBC-mode for the symmetric encryption Enc; 1,024-bit RSA for the digital signatures Sig. The simulation environment of AP is Windows XP OS over an Inter(R) Pentium IV 2.56GHz processor and 2GB memory. The hardware environment of the mobile crowd sensing has a low-power high-performance 32-bit Inter(R) PXA270 624MHz processor and 128MB memory running Windows CE 5.2 OS. For each experiment, we report the average of 10 runs.

The experiment result of our scheme is shown in Fig. 6, we can easily see that the run time grows linearly as the number of entries increases. It takes about 155ms to authenticate when the entity is 1000, which only occurs when the participant’s reputation scores don’t satisfy the policy. Otherwise, the time of authentication at AP will be less, and the run time is only about 50ms. In Update scores phase and Modify scores phase, the run time at NM and AP is about 50ms when entity is 1000, since the operations at NM and AP are similarity. Especially, we compare the run time at AP and the participant between LZCK [28] and our scheme for authentication phase. The results as shown in Fig. 7 demonstrate that our scheme generally outperforms LZCK [28], since Liu’s scheme is mainly based on bilinear pairing and our scheme is based on symmetric key cryptography. Therefore, these make it more suitable to implement for mobile crowd sensing.

Fig. 6
figure 6

The performance at a(NM) and b(AP) of various phases

Full size image
Fig. 7
figure 7

A comparison of running time between different schemes

Full size image

7 Related work

Theoretically, anonymous authentication in MCS can be implemented by traditional public-key cryptosystems (PKC) [17, 19, 20, 22]. In particular, Yang et al. [17], presents a novel password-based remote user authentication scheme using bilinear pairings by introducing the concept of private key proxy quantity. However, the computational cost on the user side is a critical issue for implementation on MCS. In [19], propose an ID-based remote mutual authentication with key agreement scheme on ECC, which is based upon the ID-based concept, and the proposed scheme does not require public keys for users so that the additional computations for certificates can be reduced. In addition, which have better performance, thanks to the smaller key size used in ECC. For example, 160-bit ECC achieves the same security level as 1,024-bit RSA. However, as most other PKC schemes, which requires a certification authority (CA) to maintain a pool of certificates for users’ public keys, and the users need extra computation to verify the certificates of others. In [20], presents a mutual authentication and key exchange scheme using bilinear pairings, which is based on the computational Diffie-Hellman assumption and the random oracle model, but this design may cost a bit of high computational and not available to implement on MCS. Therefore most of the designs are infeasible in mobile networks, because PKC needs to compute modular exponentiation which may consume more computational resource than what mobile devices can offer.

In order to prevent the abuse of anonymous environment, a few schemes [23–26] have been proposed to revoke access for misbehaving users while maintaining their anonymity. Especially, in [25], users must prove in zero knowledge that each entry on the blacklist does not correspond to an authentication made earlier using their credential, resulting in authentication times linear in the size of the blacklist, which, obviously, cannot suit for mobile device. In [23], Lin et al. propose a scalable anonymous black-listing scheme based on bilinear pairings. Obviously, that may consume much computational resource which is beyond what mobile devices can offer. Therefore, most of these schemes can not be easily implemented on MCS.

8 Conclusions

In this paper, we have utilized the blacklist technique to propose a practical anonymous scheme to preserve privacy of MCS participants when they make access to MCS terminals. Detailed secure analysis shows the proposed scheme can satisfy the desirable security requirements. Performance evaluation shows that the proposed scheme can achieve better efficiency in terms of computation overhead compared with the existing works.