# SCPR: Secure Crowdsourcing-Based Parking Reservation System

Authors: Changsheng Wan; Juan Zhang; Daoli Huang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

The crowdsourcing-based parking reservation system is a new computing paradigm, where private owners can rent their parking spots out. Security is the main concern for parking reservation systems. However, current schemes cannot provide user privacy protection for drivers and have no key agreement functions, resulting in a lot of security problems. Moreover, current schemes are typically based on the time-consuming bilinear pairing and not suitable for real-time applications. To solve these security and efficiency problems, we present a novel security protocol with user privacy called SCPR. Similar to protocols of this field, SCPR can authenticate drivers involved in the parking reservation system. However, different from other well-known approaches, SCPR uses pseudonyms instead of real identities for providing user privacy protection for drivers and designs a novel pseudonym-based key agreement protocol. Finally, to reduce the time cost, SCPR designs several novel cryptographic algorithms based on the algebraic signature technique. By doing so, SCPR can satisfy a number of security requirements and enjoy high efficiency. Experimental results show SCPR is feasible for real world applications.


---

## Body

## 1. Introduction

As the amount of cars increases explosively, parking is becoming a precious resource in crowded urban areas such as New York and San Francisco [1]. To fully use parking spots that belong to “private owners (PO),” crowdsourcing-based parking reservation systems have been proposed [2, 3], where private owners can publish rental information to the “Service Provider (SP),” while other “Tenant Drivers (TD)” can download rental information from SP and make a reservation.User privacy [4] is the basic concern for the above parking reservation system. Due to the openness of the website of SP, it is easy for malicious advertisers to download PO’s private information (e.g., real identities such as user name or driver license) and annoy him by keeping on sending cheating advertisements. Moreover, during the reservation process, a terrorist may even trace the PO or the TD and establish a serious terrorist attack. Therefore, it is important to use pseudonyms instead of users’ real identities in this parking reservation system, so that both cheating advertisements and terrorist attacks can be avoided. However, current crowdsourcing-based security protocols (i.e., [5–30]) are still based on real identities of PO and TD. So, to provide user privacy protection, it is urgent to develop a pseudonym-based security protocol for crowdsourcing-based parking reservation systems.On the other hand, time cost is another serious concern for parking reservation systems. Due to the high speed of cars, the parking reservation system is a real-time application [11]. So the PO and the TD are seriously concerned about high time cost arising from running cryptographic operations. Therefore, to reduce time cost, it is desirable to use highly efficient cryptographic operations for designing security protocols for parking reservation systems. Unfortunately, current crowdsourcing-based security protocols are mainly based on the time-consuming bilinear pairing operations [5, 6]. So, to reduce time cost, it is important to develop a security protocol for crowdsourcing-based parking reservation systems without bilinear pairing.Taking both user privacy and time cost into account, we shall design a pseudonym-based security protocol for crowdsourcing-based parking reservation systems without bilinear pairing. This security protocol should satisfy the following requirements.(1) User Privacy. It should be guaranteed that real identities of the PO and the TD (e.g., user name or driver license) will not be extracted by an adversary. Without user privacy, the adversary may send cheating advertisements to the PO and the TD and trace them.(2) Integrity of Rental Information. It should be guaranteed that the rental information will not be tampered by an adversary. Without integrity of rental information, the TD may download wrong rental information, resulting in parking failure.(3) Authentication. It should be guaranteed that the PO and the TD are authenticated. Without authentication, an adversary may impersonate the TD or the PO, resulting in economic losses of the PO or the TD.(4) Key Agreement. It should be guaranteed that the PO and the TD can negotiate a shared key for protecting subsequent transactions. Specifically, it should be guaranteed that the shared key will not be tampered or extracted by an adversary. Without key agreement, the subsequent transactions may be compromised by an adversary, resulting in reservation failure.(5) Time Costs. It should be guaranteed that the time cost between the PO and the TD is low. Time cost is comprised of computation and communication costs. Computation cost is mainly consumed by cryptographic algorithms on the PO and the TD, while communication cost is mainly consumed by message-transmitting processes between the PO and the TD.Obviously, designing a security protocol for crowdsourcing-based parking reservation systems is a nontrivial task, due to its complicated security and efficiency requirements as discussed above. Currently, requirement (3) has been well addressed in the literature. But, the other requirements (i.e., user privacy, integrity of rental information, key agreement, and time cost) have been largely neglected. More importantly, when considering this research topic, we find that there is no security primitive which can be directly deployed for satisfying all the above requirements. The detailed analysis for drawing this conclusion will be given in Section2. This becomes a more urgent problem, with the deployment of parking reservation systems in real world. Motivated by this observation, we make three contributions, as described below.(1)
We discuss some security and efficiency issues in crowdsourcing-based parking reservation systems and then list a set of important requirements.(2)
We present a novel security protocol called SCPR that can fulfill all the above requirements. However, different from current crowdsourcing-based security protocols built on real identities, SCPR is based on pseudonyms. By doing so, the user privacy requirement can be fulfilled. Then, observing that the key agreement requirement is not fulfilled by current security protocols, we design a novel pseudonym-based key agreement protocol that can generate a shared key for protecting subsequent reservation transactions. Finally, observing that bilinear pairing operation is low efficient, we shall use algebraic signature [31] for designing the above security protocol. By doing so, the time cost of SCPR can be significantly reduced.(3)
We analyze the security of SCPR, showing it can fulfill requirements (1), (2), (3), and (4). And we evaluate the efficiency of SCPR, showing it can fulfill requirement (5).The remainder of this paper is organized below. In Section2, we discuss the related work. Then, in Section 3, we propose the SCPR protocol, followed by security analysis and efficiency evaluation in Sections 4 and 5, respectively. Finally, we draw our conclusions in Section 6.


## 2. Related Work

Due to its convenience, crowdsourcing has become more and more popular. For instance, [5] designed a crowdsourcing-based mobile-healthcare system. The paper [12] is a crowdsourcing-based city governance system. The paper [20] is a crowdsourcing-based system for enterprises. DYSWIS [25] introduced a crowdsourcing-based home network system. The papers [6, 21, 26] combined the cloud computing technique with crowdsourcing-based systems. The paper [27] introduced a location-based crowdsourcing scheme. The papers [18, 22] discussed the deployment of crowdsourcing technique in parking systems.Security is the main concern for crowdsourcing-based systems. Recently, a lot of works have been focusing on this topic. For instance, [4, 7, 15, 29] analyzed the privacy-preserving and integrity of transmitted data. The paper [14] discussed the establishment of trust relationships in crowdsourcing-based systems. However, there are three issues with current works as shown below.First, various applications may have different security requirements. For instance, in mobile-healthcare systems [5], privacy of transmitted data (personal health information) is the most important requirement, while in city governance systems [12], access control has vital significance. The security requirements of parking reservation systems are different from those of other crowdsourcing-based systems too, as discussed in Section 1. Therefore, it is desired to classify the security requirements for parking reservation systems.Second, parking reservation systems have some special security requirements that have not been discussed by current works. For instance, in most of current protocols [5, 12, 20], real identities are used directly. However, for parking reservation systems, this may lead to a variety of security issues as discussed in Section 1. Therefore, it is desired to design a new security protocol for fulfilling those security requirements.Third, current crowdsourcing-based parking reservation systems [18, 22] mainly focused on the data transmitting model and did not provide security protocols. For instance, [18] discussed the detailed transactions of parking reservation without designing security protocols for protecting the transactions, while [22] discussed several security issues of parking reservation systems without corresponding solutions. Therefore, it is desired to design security protocols for parking reservation systems.At the same time, time cost is another serious concern for crowdsourcing-based systems [11, 28]. For instance, the crowdsourcing-based parking systems [18, 22] required the parking reservation protocols being executed quickly due to the high speed of cars, while the crowdsourcing-based video systems [9] required the time cost to be low due to the large amount of video data to be processed. However, current security protocols for crowdsourcing systems are mainly built on time-consuming bilinear maps. For instance, in [5, 6], both the TD and the PO have to run the pairing algorithm several times, resulting in high time cost. In Section 5, we will show that the pairing algorithm consumes much more time than other cryptographic algorithms. Therefore, it is desired to design security protocols for parking reservation systems using efficient cryptographic algorithms.


## 3. SCPR: The Protocol

### 3.1. Preliminaries

The algebraic signature [31] technique includes two processes.The Signing Process. Given a set of secret keys SK={ski∈Zp,1≤i≤n}, the algebraic signature for a binary string s=s1s2⋯sn, where si∈{0,1},1≤i≤n, is generated as σ=∑i=1n‍siskimodp.The Verification Process. Given a binary string s=s1s2⋯sn, where si∈{0,1},1≤i≤n, and the corresponding algebraic signature σ, the verifier computes σ′=∑i=1n‍siskimodp and checks σ′=?σ to determine whether s is tampered by an attacker.The above algebraic signature employs only several addition and modular multiplication operations. Therefore, it is highly efficient.


### 3.2. System Model

The system model of SCPR is shown in Figure1, which includes three phases as illustrated below, and the notations in this paper are listed in Notations.Figure 1
System model of SCPR.


#### 3.2.1. The Key-Distributing Phase

During the key-distributing phase, the SP first initializes SCPR by generating public and private system parameters. The public system parameters will be distributed to the PO and the TD, while the private system parameters will be hold by the SP. The initialization algorithm is illustrated below.{
S
K
S
P
,
P
K
S
P
}
←
I
n
i
t
(
n
). This algorithm is run by the SP for initializing system parameters for SCPR. It takes as input the parameter of security level (i.e., n) and outputs a set of private system parameters (i.e., SKSP) and the corresponding set of public system parameters (i.e., PKSP).Before publishing rental information, the PO sends a request to the SP. Upon receiving the request, the SP generates a pseudonym and a private key and distributes them to the PO over their preestablished secure channel, using the followingRegPO algorithm.{
P
P
O
,
S
K
P
O
}
←
R
e
g
P
O
(
R
I
D
P
O
,
S
K
S
P
,
P
K
S
P
). This algorithm is run by the SP for generating a pseudonym and a private key for the PO. It takes as inputs PO’s real identity (i.e., RIDPO), the set of private system parameters (i.e., SKSP), and the set of public system parameters (i.e., PKSP) and outputs PO’s pseudonym (i.e., PPO) and a private key (i.e., SKPO).Before making a parking reservation, the TD sends a request to the SP. Upon receiving the request, the SP generates a pseudonym and a private key and distributes them to the TD over their preestablished secure channel, using the followingRegTD algorithm.{
P
T
D
,
S
K
T
D
}
←
R
e
g
T
D
(
R
I
D
T
D
,
S
K
S
P
,
P
K
S
P
). This algorithm is run by the SP for generating a pseudonym and a private key for the TD. It takes as inputs TD’s real identity (i.e., RIDTD), the set of private system parameters (i.e., SKSP), and the set of public system parameters (i.e., PKSP) and outputs TD’s pseudonym (i.e., PTD) and a private key (i.e., SKTD).After the key-distributing phase, the PO holds the tuple(PPO,SKPO,PKSP), and the TD holds the tuple (PTD,SKTD,PKSP).


#### 3.2.2. The Publishing Phase

When the PO wants to publish its rental information, it randomly generates a secret key (i.e.,SKRI∈Zp) and signs the rental information using SKRI. The signing algorithm is illustrated below.σ
R
I
←
S
i
g
n
R
I
(
R
I
,
S
K
R
I
). This algorithm is run by the SP for signing the rental information (i.e., RI). It takes as inputs RI and the secret key (i.e., SKRI) and outputs a signature (i.e., σRI) for RI.After the publishing phase, the PO holdsSKRI, and the SP gets the rental information (i.e., RI) and the signature (i.e., σRI).


#### 3.2.3. The Authentication and Key Agreement Phase

The authentication and key agreement phase is carried out between the PO and the TD. During this phase, the TD and the PO authenticate each other and negotiate a shared key for protecting subsequent transactions. Then the PO sendsSKRI to the TD for checking the integrity of the rental information. The authentication and key agreement phase includes three steps as illustrated below.Step 1.
The TD establishes the authentication and key agreement phase by generating a nonce (i.e.,N) and the corresponding signature (i.e., σN) using its own private key (i.e., SKTD). Then, the TD sends N and σN to the PO for authentication. The signing algorithm for N is illustrated below.
{
σ
N
}
←
S
i
g
n
N
(
N
,
P
P
O
,
P
K
S
P
,
S
K
T
D
). This algorithm is run by the TD for generating a signature for the nonce. It takes as inputs the nonce (i.e., N), the PO’s pseudonym (i.e., PPO), the set of public system parameters (i.e., PKSP), and the TD’s private key (i.e., SKTD) and outputs a signature (i.e., σN).Step 2.
When receivingN and σN from the TD, the PO checks them to authenticate the TD, using its private key (i.e., SKPO) and the following VerN algorithm. If the verification succeeds, the PO generates the shared key (i.e., sk) from N using the following KeygenPO algorithm. Finally, the PO signs and encrypts SKRI using sk and the following Senck algorithm and sends the signed and encrypted message to the TD. The VerN, KeygenPO, and Senck algorithms are illustrated below.
{
T
,
F
}
←
V
e
r
N
(
N
,
σ
N
,
S
K
P
O
,
P
T
D
,
P
K
S
P
). This algorithm is run by the PO for authenticating the TD. It takes as inputs the nonce (i.e., N), the signature (i.e., σN), PO’s private key (i.e., SKPO), TD’s pseudonym (i.e., PTD), and the set of public system parameters (i.e., PKSP) and outputs T if the verification succeeds, or F otherwise.
{
s
k
}
←
K
e
y
g
e
n
P
O
(
N
,
S
K
P
O
,
P
T
D
,
P
K
S
P
). This algorithm is run by the PO for generating the shared key. It takes as inputs the nonce (i.e., N), PO’s private key (i.e., SKPO), TD’s pseudonym (i.e., PTD), and the set of public system parameters (i.e., PKSP) and outputs the shared key (i.e., sk).
{
τ
}
←
S
e
n
c
k
(
P
K
S
P
,
s
k
,
S
K
R
I
). This algorithm is run by the PO for signing and encrypting SKRI. It takes as inputs the set of public system parameters (i.e., PKSP), the shared key (i.e., sk), and the publishing key (i.e., SKRI) and outputs a signed and encrypted message (i.e., τ).Step 3.
Upon gettingτ from the PO, the TD first generates the shared key (i.e., sk) using the following KeygenTD algorithm. Then, it decrypts and verifies τ to extract SKRI and to authenticate the PO, using the following Vdeck algorithm. Finally, the TD verifies RI and σRI downloaded from the SP to make sure it is not tamped by an adversary, using SKRI and the following VerRI algorithm. The KeygenTD, Vdeck, and VerRI algorithms are illustrated below.
{
s
k
}
←
K
e
y
g
e
n
T
D
(
N
,
S
K
T
D
,
P
P
O
,
P
K
S
P
). This algorithm is run by the TD for generating the shared key. It takes as inputs the nonce (i.e., N), TD’s private key (i.e., SKTD), PO’s pseudonym (i.e., PPO), and the set of public system parameters (i.e., PKSP) and outputs the shared key (i.e., sk).
{
S
K
R
I
,
{
T
,
F
}
}
←
V
d
e
c
k
(
τ
,
s
k
,
P
K
S
P
). This algorithm is run by the TD for decrypting and verifying the publishing key and authenticating PO. It takes as inputs the data to be decrypted and verified (i.e., τ), the shared key (i.e., sk), and the set of public system parameters (i.e., PKSP) and outputs the publishing key (i.e., SKRI). Then, it outputs T if SKRI can pass the verification and the PO is authenticated, or F otherwise.
{
T
,
F
}
←
V
e
r
R
I
(
R
I
,
σ
R
I
,
S
K
R
I
,
P
K
S
P
). This algorithm is run by the TD for verifying the rental information downloaded from the SP. It takes as inputs the rental information (i.e., RI), the signature (i.e., σRI), the publishing key (i.e., SKRI), and the set of public system parameters (i.e., PKSP) and outputs T if RI can pass the verification, or F otherwise.After the above three phases, the PO and the TD are both authenticated and a shared key (i.e.,sk) is generated for protecting the subsequent transactions between them.From this system model, it can be seen that the PO and the TD use pseudonyms instead of their real identities. Therefore, SCPR can satisfy requirement (1) described in Section1 (i.e., user privacy). In Section 4, we will further analyze requirement (1).From this system model, it can be seen that the rental information (i.e.,RI) is signed. Therefore, SCPR can satisfy requirement (2) described in Section 1 (i.e., integrity of rental information). In Section 4, we will further analyze requirement (2).From this system model, it can be seen that both the PO and the TD are authenticated, and a shared key is generated between them. Therefore, SCPR can satisfy requirements (3) and (4) described in Section1 (i.e., authentication and key agreement). In Section 4, we will further analyze requirements (3) and (4).


### 3.3. Construction

The construction of SCPR is a tuple (Init, RegPO, RegTD, SignRI, VerRI, SignN, VerN, KeygenPO, KeygenTD, Senck, and Vdeck) of probabilistic polynomial time algorithms as illustrated below.{
S
K
S
P
,
P
K
S
P
}
←
I
n
i
t
(
n
). The SP runs this algorithm for generating system parameters for SCPR as follows. First, the SP generates a group G with a prime order p and a generator g, where n is the security level determining the key length in bit, the length of p is n-bit, and g is a randomly picked element in G. Second, the SP randomly generates a set of private keys SKSP={skpox∈Zp,sktdx∈Zp,1≤x≤n}. Third, for each skpox∈SKSP and sktdx∈SKSP, the SP computes pkpox=gskpox∈G and pktdx=gsktdx∈G and gets the set of public system parameters PKSP={G,p,g,pkpox,pktdx,1≤x≤n}.{
P
P
O
,
S
K
P
O
}
←
R
e
g
P
O
(
R
I
D
P
O
,
S
K
S
P
,
P
K
S
P
). The SP runs this algorithm for generating a pseudonym and a private key for the PO as follows. First, the SP generates PO’s pseudonym as PPO=h1(RIDPO), where h1:Zp→Zp is a hash function. Second, the SP computes a1⋯an=h2(PPO) and takes the algebraic signature SKPO=∑x=1n‍axskpoxmodp as the PO’s private key, where h2:Zp→{0,1}n is a hash function, and a1,…,an∈{0,1}.{
P
T
D
,
S
K
T
D
}
←
R
e
g
T
D
(
R
I
D
T
D
,
S
K
S
P
,
P
K
S
P
). The SP runs this algorithm for generating a pseudonym and a private key for the TD as follows. First, the SP generates TD’s pseudonym as PTD=h1(RIDTD), where h1:Zp→Zp is a hash function. Second, the SP computes b1⋯bn=h2(PTD) and takes the algebraic signature SKTD=∑x=1n‍bxsktdxmodp as the TD’s private key, where h2:Zp→{0,1}n is a hash function, and b1,…,bn∈{0,1}.σ
R
I
←
S
i
g
n
R
I
(
R
I
,
S
K
R
I
). The PO runs this algorithm for generating a signature for the rental information as σRI=h1(RI∣SKRI), where h1:Zp→Zp is a hash function.{
σ
N
}
←
S
i
g
n
N
(
N
,
P
P
O
,
P
K
S
P
,
S
K
T
D
). The TD runs this algorithm for generating a signature for the nonce as follows. First, the TD computes PKPO=∏x=1n‍pkpoxax∈G, where a1⋯an=h2(PPO). Second, the TD computes σN=h1(N∣H(PKPOSKTD)), where h2:Zp→{0,1}n, H:G→Zp, and h1:Zp→Zp are hash functions.{
T
,
F
}
←
V
e
r
N
(
N
,
σ
N
,
S
K
P
O
,
P
T
D
,
P
K
S
P
). The PO runs this algorithm for authenticating the TD as follows. First, the PO computes PKTD=∏x=1n‍pktdxbx∈G, where b1⋯bn=h2(PTD). Second, the PO computes σN′=h1(N∣H(PKTDSKPO)) and checks σN′=?σN. If this equation holds, PO returns T. Otherwise, it returns F.{
s
k
}
←
K
e
y
g
e
n
P
O
(
N
,
S
K
P
O
,
P
T
D
,
P
K
S
P
). The PO runs this algorithm for generating the shared key as follows. First, the PO computes PKTD=∏x=1n‍pktdxbx∈G, where b1⋯bn=h2(PTD), PTD is the pseudonym of TD, and pktdx∈PKSP(x∈{1,…,n}) are distributed from the SP during the initialization phase. Second, the PO computes sk=PKTDSKPON∈G.{
τ
}
←
S
e
n
c
k
(
P
K
S
P
,
s
k
,
S
K
R
I
). The PO runs this algorithm for signing and encrypting SKRI as follows. First, the PO encrypts SKRI as c1=H(sk)⊕SKRImodp, where H:G→Zp is a hash function. Second, the PO signs SKRI as c2=h1(SKRI∣H(sk)), where H:G→Zp and h1:Zp→Zp are hash functions. Finally, the PO gets τ=(c1,c2).{
s
k
}
←
K
e
y
g
e
n
T
D
(
N
,
S
K
T
D
,
P
P
O
,
P
K
S
P
). The TD runs this algorithm for generating the shared key as follows. First, the TD computes PKPO=∏x=1n‍pkpoxax∈G, where a1⋯an=h2(PPO), PPO is the pseudonym of PO, and pkpox∈PKSP(x∈{1,…,n}) are distributed from the SP during the initialization phase. Second, the TD computes sk=PKPOSKTDN∈G.{
S
K
R
I
,
{
T
,
F
}
}
←
V
d
e
c
k
(
τ
,
s
k
,
P
K
S
P
). The TD runs this algorithm for decrypting and verifying the publishing key as follows. First, the TD decrypts SKRI as SKRI=c1⊕H(sk)modp, where H:G→Zp is a hash function. Second, the TD computes c2′=h1(SKRI∣H(sk)) and checks c2′=?c2, where H:G→Zp and h1:Zp→Zp are hash functions. If c2′=c2, the TD returns (SKRI,T). Otherwise, it returns F.{
T
,
F
}
←
V
e
r
R
I
(
R
I
,
σ
R
I
,
S
K
R
I
,
P
K
S
P
). The TD runs this algorithm for verifying the rental information as follows. First, the TD computes σRI′=h1(RI∣SKRI), where h1:Zp→Zp is a hash function. Second, the TD checks σRI′=?σRI. If this equation holds, TD returns T. Otherwise, it returns F.From this construction, it can be seen that SCPR does not use bilinear map. In fact, it employs only a few modular exponentiations, which is quite efficient. We will further evaluate the efficiency of SCPR in Section5. Note that, when computing PKPO and PKTD, there is no modular exponentiation, because ax∈{0,1} and bx∈{0,1}. So our construction is highly efficient.


## 3.1. Preliminaries

The algebraic signature [31] technique includes two processes.The Signing Process. Given a set of secret keys SK={ski∈Zp,1≤i≤n}, the algebraic signature for a binary string s=s1s2⋯sn, where si∈{0,1},1≤i≤n, is generated as σ=∑i=1n‍siskimodp.The Verification Process. Given a binary string s=s1s2⋯sn, where si∈{0,1},1≤i≤n, and the corresponding algebraic signature σ, the verifier computes σ′=∑i=1n‍siskimodp and checks σ′=?σ to determine whether s is tampered by an attacker.The above algebraic signature employs only several addition and modular multiplication operations. Therefore, it is highly efficient.


## 3.2. System Model

The system model of SCPR is shown in Figure1, which includes three phases as illustrated below, and the notations in this paper are listed in Notations.Figure 1
System model of SCPR.


### 3.2.1. The Key-Distributing Phase

During the key-distributing phase, the SP first initializes SCPR by generating public and private system parameters. The public system parameters will be distributed to the PO and the TD, while the private system parameters will be hold by the SP. The initialization algorithm is illustrated below.{
S
K
S
P
,
P
K
S
P
}
←
I
n
i
t
(
n
). This algorithm is run by the SP for initializing system parameters for SCPR. It takes as input the parameter of security level (i.e., n) and outputs a set of private system parameters (i.e., SKSP) and the corresponding set of public system parameters (i.e., PKSP).Before publishing rental information, the PO sends a request to the SP. Upon receiving the request, the SP generates a pseudonym and a private key and distributes them to the PO over their preestablished secure channel, using the followingRegPO algorithm.{
P
P
O
,
S
K
P
O
}
←
R
e
g
P
O
(
R
I
D
P
O
,
S
K
S
P
,
P
K
S
P
). This algorithm is run by the SP for generating a pseudonym and a private key for the PO. It takes as inputs PO’s real identity (i.e., RIDPO), the set of private system parameters (i.e., SKSP), and the set of public system parameters (i.e., PKSP) and outputs PO’s pseudonym (i.e., PPO) and a private key (i.e., SKPO).Before making a parking reservation, the TD sends a request to the SP. Upon receiving the request, the SP generates a pseudonym and a private key and distributes them to the TD over their preestablished secure channel, using the followingRegTD algorithm.{
P
T
D
,
S
K
T
D
}
←
R
e
g
T
D
(
R
I
D
T
D
,
S
K
S
P
,
P
K
S
P
). This algorithm is run by the SP for generating a pseudonym and a private key for the TD. It takes as inputs TD’s real identity (i.e., RIDTD), the set of private system parameters (i.e., SKSP), and the set of public system parameters (i.e., PKSP) and outputs TD’s pseudonym (i.e., PTD) and a private key (i.e., SKTD).After the key-distributing phase, the PO holds the tuple(PPO,SKPO,PKSP), and the TD holds the tuple (PTD,SKTD,PKSP).


### 3.2.2. The Publishing Phase

When the PO wants to publish its rental information, it randomly generates a secret key (i.e.,SKRI∈Zp) and signs the rental information using SKRI. The signing algorithm is illustrated below.σ
R
I
←
S
i
g
n
R
I
(
R
I
,
S
K
R
I
). This algorithm is run by the SP for signing the rental information (i.e., RI). It takes as inputs RI and the secret key (i.e., SKRI) and outputs a signature (i.e., σRI) for RI.After the publishing phase, the PO holdsSKRI, and the SP gets the rental information (i.e., RI) and the signature (i.e., σRI).


### 3.2.3. The Authentication and Key Agreement Phase

The authentication and key agreement phase is carried out between the PO and the TD. During this phase, the TD and the PO authenticate each other and negotiate a shared key for protecting subsequent transactions. Then the PO sendsSKRI to the TD for checking the integrity of the rental information. The authentication and key agreement phase includes three steps as illustrated below.Step 1.
The TD establishes the authentication and key agreement phase by generating a nonce (i.e.,N) and the corresponding signature (i.e., σN) using its own private key (i.e., SKTD). Then, the TD sends N and σN to the PO for authentication. The signing algorithm for N is illustrated below.
{
σ
N
}
←
S
i
g
n
N
(
N
,
P
P
O
,
P
K
S
P
,
S
K
T
D
). This algorithm is run by the TD for generating a signature for the nonce. It takes as inputs the nonce (i.e., N), the PO’s pseudonym (i.e., PPO), the set of public system parameters (i.e., PKSP), and the TD’s private key (i.e., SKTD) and outputs a signature (i.e., σN).Step 2.
When receivingN and σN from the TD, the PO checks them to authenticate the TD, using its private key (i.e., SKPO) and the following VerN algorithm. If the verification succeeds, the PO generates the shared key (i.e., sk) from N using the following KeygenPO algorithm. Finally, the PO signs and encrypts SKRI using sk and the following Senck algorithm and sends the signed and encrypted message to the TD. The VerN, KeygenPO, and Senck algorithms are illustrated below.
{
T
,
F
}
←
V
e
r
N
(
N
,
σ
N
,
S
K
P
O
,
P
T
D
,
P
K
S
P
). This algorithm is run by the PO for authenticating the TD. It takes as inputs the nonce (i.e., N), the signature (i.e., σN), PO’s private key (i.e., SKPO), TD’s pseudonym (i.e., PTD), and the set of public system parameters (i.e., PKSP) and outputs T if the verification succeeds, or F otherwise.
{
s
k
}
←
K
e
y
g
e
n
P
O
(
N
,
S
K
P
O
,
P
T
D
,
P
K
S
P
). This algorithm is run by the PO for generating the shared key. It takes as inputs the nonce (i.e., N), PO’s private key (i.e., SKPO), TD’s pseudonym (i.e., PTD), and the set of public system parameters (i.e., PKSP) and outputs the shared key (i.e., sk).
{
τ
}
←
S
e
n
c
k
(
P
K
S
P
,
s
k
,
S
K
R
I
). This algorithm is run by the PO for signing and encrypting SKRI. It takes as inputs the set of public system parameters (i.e., PKSP), the shared key (i.e., sk), and the publishing key (i.e., SKRI) and outputs a signed and encrypted message (i.e., τ).Step 3.
Upon gettingτ from the PO, the TD first generates the shared key (i.e., sk) using the following KeygenTD algorithm. Then, it decrypts and verifies τ to extract SKRI and to authenticate the PO, using the following Vdeck algorithm. Finally, the TD verifies RI and σRI downloaded from the SP to make sure it is not tamped by an adversary, using SKRI and the following VerRI algorithm. The KeygenTD, Vdeck, and VerRI algorithms are illustrated below.
{
s
k
}
←
K
e
y
g
e
n
T
D
(
N
,
S
K
T
D
,
P
P
O
,
P
K
S
P
). This algorithm is run by the TD for generating the shared key. It takes as inputs the nonce (i.e., N), TD’s private key (i.e., SKTD), PO’s pseudonym (i.e., PPO), and the set of public system parameters (i.e., PKSP) and outputs the shared key (i.e., sk).
{
S
K
R
I
,
{
T
,
F
}
}
←
V
d
e
c
k
(
τ
,
s
k
,
P
K
S
P
). This algorithm is run by the TD for decrypting and verifying the publishing key and authenticating PO. It takes as inputs the data to be decrypted and verified (i.e., τ), the shared key (i.e., sk), and the set of public system parameters (i.e., PKSP) and outputs the publishing key (i.e., SKRI). Then, it outputs T if SKRI can pass the verification and the PO is authenticated, or F otherwise.
{
T
,
F
}
←
V
e
r
R
I
(
R
I
,
σ
R
I
,
S
K
R
I
,
P
K
S
P
). This algorithm is run by the TD for verifying the rental information downloaded from the SP. It takes as inputs the rental information (i.e., RI), the signature (i.e., σRI), the publishing key (i.e., SKRI), and the set of public system parameters (i.e., PKSP) and outputs T if RI can pass the verification, or F otherwise.After the above three phases, the PO and the TD are both authenticated and a shared key (i.e.,sk) is generated for protecting the subsequent transactions between them.From this system model, it can be seen that the PO and the TD use pseudonyms instead of their real identities. Therefore, SCPR can satisfy requirement (1) described in Section1 (i.e., user privacy). In Section 4, we will further analyze requirement (1).From this system model, it can be seen that the rental information (i.e.,RI) is signed. Therefore, SCPR can satisfy requirement (2) described in Section 1 (i.e., integrity of rental information). In Section 4, we will further analyze requirement (2).From this system model, it can be seen that both the PO and the TD are authenticated, and a shared key is generated between them. Therefore, SCPR can satisfy requirements (3) and (4) described in Section1 (i.e., authentication and key agreement). In Section 4, we will further analyze requirements (3) and (4).


## 3.2.1. The Key-Distributing Phase

During the key-distributing phase, the SP first initializes SCPR by generating public and private system parameters. The public system parameters will be distributed to the PO and the TD, while the private system parameters will be hold by the SP. The initialization algorithm is illustrated below.{
S
K
S
P
,
P
K
S
P
}
←
I
n
i
t
(
n
). This algorithm is run by the SP for initializing system parameters for SCPR. It takes as input the parameter of security level (i.e., n) and outputs a set of private system parameters (i.e., SKSP) and the corresponding set of public system parameters (i.e., PKSP).Before publishing rental information, the PO sends a request to the SP. Upon receiving the request, the SP generates a pseudonym and a private key and distributes them to the PO over their preestablished secure channel, using the followingRegPO algorithm.{
P
P
O
,
S
K
P
O
}
←
R
e
g
P
O
(
R
I
D
P
O
,
S
K
S
P
,
P
K
S
P
). This algorithm is run by the SP for generating a pseudonym and a private key for the PO. It takes as inputs PO’s real identity (i.e., RIDPO), the set of private system parameters (i.e., SKSP), and the set of public system parameters (i.e., PKSP) and outputs PO’s pseudonym (i.e., PPO) and a private key (i.e., SKPO).Before making a parking reservation, the TD sends a request to the SP. Upon receiving the request, the SP generates a pseudonym and a private key and distributes them to the TD over their preestablished secure channel, using the followingRegTD algorithm.{
P
T
D
,
S
K
T
D
}
←
R
e
g
T
D
(
R
I
D
T
D
,
S
K
S
P
,
P
K
S
P
). This algorithm is run by the SP for generating a pseudonym and a private key for the TD. It takes as inputs TD’s real identity (i.e., RIDTD), the set of private system parameters (i.e., SKSP), and the set of public system parameters (i.e., PKSP) and outputs TD’s pseudonym (i.e., PTD) and a private key (i.e., SKTD).After the key-distributing phase, the PO holds the tuple(PPO,SKPO,PKSP), and the TD holds the tuple (PTD,SKTD,PKSP).


## 3.2.2. The Publishing Phase

When the PO wants to publish its rental information, it randomly generates a secret key (i.e.,SKRI∈Zp) and signs the rental information using SKRI. The signing algorithm is illustrated below.σ
R
I
←
S
i
g
n
R
I
(
R
I
,
S
K
R
I
). This algorithm is run by the SP for signing the rental information (i.e., RI). It takes as inputs RI and the secret key (i.e., SKRI) and outputs a signature (i.e., σRI) for RI.After the publishing phase, the PO holdsSKRI, and the SP gets the rental information (i.e., RI) and the signature (i.e., σRI).


## 3.2.3. The Authentication and Key Agreement Phase

The authentication and key agreement phase is carried out between the PO and the TD. During this phase, the TD and the PO authenticate each other and negotiate a shared key for protecting subsequent transactions. Then the PO sendsSKRI to the TD for checking the integrity of the rental information. The authentication and key agreement phase includes three steps as illustrated below.Step 1.
The TD establishes the authentication and key agreement phase by generating a nonce (i.e.,N) and the corresponding signature (i.e., σN) using its own private key (i.e., SKTD). Then, the TD sends N and σN to the PO for authentication. The signing algorithm for N is illustrated below.
{
σ
N
}
←
S
i
g
n
N
(
N
,
P
P
O
,
P
K
S
P
,
S
K
T
D
). This algorithm is run by the TD for generating a signature for the nonce. It takes as inputs the nonce (i.e., N), the PO’s pseudonym (i.e., PPO), the set of public system parameters (i.e., PKSP), and the TD’s private key (i.e., SKTD) and outputs a signature (i.e., σN).Step 2.
When receivingN and σN from the TD, the PO checks them to authenticate the TD, using its private key (i.e., SKPO) and the following VerN algorithm. If the verification succeeds, the PO generates the shared key (i.e., sk) from N using the following KeygenPO algorithm. Finally, the PO signs and encrypts SKRI using sk and the following Senck algorithm and sends the signed and encrypted message to the TD. The VerN, KeygenPO, and Senck algorithms are illustrated below.
{
T
,
F
}
←
V
e
r
N
(
N
,
σ
N
,
S
K
P
O
,
P
T
D
,
P
K
S
P
). This algorithm is run by the PO for authenticating the TD. It takes as inputs the nonce (i.e., N), the signature (i.e., σN), PO’s private key (i.e., SKPO), TD’s pseudonym (i.e., PTD), and the set of public system parameters (i.e., PKSP) and outputs T if the verification succeeds, or F otherwise.
{
s
k
}
←
K
e
y
g
e
n
P
O
(
N
,
S
K
P
O
,
P
T
D
,
P
K
S
P
). This algorithm is run by the PO for generating the shared key. It takes as inputs the nonce (i.e., N), PO’s private key (i.e., SKPO), TD’s pseudonym (i.e., PTD), and the set of public system parameters (i.e., PKSP) and outputs the shared key (i.e., sk).
{
τ
}
←
S
e
n
c
k
(
P
K
S
P
,
s
k
,
S
K
R
I
). This algorithm is run by the PO for signing and encrypting SKRI. It takes as inputs the set of public system parameters (i.e., PKSP), the shared key (i.e., sk), and the publishing key (i.e., SKRI) and outputs a signed and encrypted message (i.e., τ).Step 3.
Upon gettingτ from the PO, the TD first generates the shared key (i.e., sk) using the following KeygenTD algorithm. Then, it decrypts and verifies τ to extract SKRI and to authenticate the PO, using the following Vdeck algorithm. Finally, the TD verifies RI and σRI downloaded from the SP to make sure it is not tamped by an adversary, using SKRI and the following VerRI algorithm. The KeygenTD, Vdeck, and VerRI algorithms are illustrated below.
{
s
k
}
←
K
e
y
g
e
n
T
D
(
N
,
S
K
T
D
,
P
P
O
,
P
K
S
P
). This algorithm is run by the TD for generating the shared key. It takes as inputs the nonce (i.e., N), TD’s private key (i.e., SKTD), PO’s pseudonym (i.e., PPO), and the set of public system parameters (i.e., PKSP) and outputs the shared key (i.e., sk).
{
S
K
R
I
,
{
T
,
F
}
}
←
V
d
e
c
k
(
τ
,
s
k
,
P
K
S
P
). This algorithm is run by the TD for decrypting and verifying the publishing key and authenticating PO. It takes as inputs the data to be decrypted and verified (i.e., τ), the shared key (i.e., sk), and the set of public system parameters (i.e., PKSP) and outputs the publishing key (i.e., SKRI). Then, it outputs T if SKRI can pass the verification and the PO is authenticated, or F otherwise.
{
T
,
F
}
←
V
e
r
R
I
(
R
I
,
σ
R
I
,
S
K
R
I
,
P
K
S
P
). This algorithm is run by the TD for verifying the rental information downloaded from the SP. It takes as inputs the rental information (i.e., RI), the signature (i.e., σRI), the publishing key (i.e., SKRI), and the set of public system parameters (i.e., PKSP) and outputs T if RI can pass the verification, or F otherwise.After the above three phases, the PO and the TD are both authenticated and a shared key (i.e.,sk) is generated for protecting the subsequent transactions between them.From this system model, it can be seen that the PO and the TD use pseudonyms instead of their real identities. Therefore, SCPR can satisfy requirement (1) described in Section1 (i.e., user privacy). In Section 4, we will further analyze requirement (1).From this system model, it can be seen that the rental information (i.e.,RI) is signed. Therefore, SCPR can satisfy requirement (2) described in Section 1 (i.e., integrity of rental information). In Section 4, we will further analyze requirement (2).From this system model, it can be seen that both the PO and the TD are authenticated, and a shared key is generated between them. Therefore, SCPR can satisfy requirements (3) and (4) described in Section1 (i.e., authentication and key agreement). In Section 4, we will further analyze requirements (3) and (4).


## 3.3. Construction

The construction of SCPR is a tuple (Init, RegPO, RegTD, SignRI, VerRI, SignN, VerN, KeygenPO, KeygenTD, Senck, and Vdeck) of probabilistic polynomial time algorithms as illustrated below.{
S
K
S
P
,
P
K
S
P
}
←
I
n
i
t
(
n
). The SP runs this algorithm for generating system parameters for SCPR as follows. First, the SP generates a group G with a prime order p and a generator g, where n is the security level determining the key length in bit, the length of p is n-bit, and g is a randomly picked element in G. Second, the SP randomly generates a set of private keys SKSP={skpox∈Zp,sktdx∈Zp,1≤x≤n}. Third, for each skpox∈SKSP and sktdx∈SKSP, the SP computes pkpox=gskpox∈G and pktdx=gsktdx∈G and gets the set of public system parameters PKSP={G,p,g,pkpox,pktdx,1≤x≤n}.{
P
P
O
,
S
K
P
O
}
←
R
e
g
P
O
(
R
I
D
P
O
,
S
K
S
P
,
P
K
S
P
). The SP runs this algorithm for generating a pseudonym and a private key for the PO as follows. First, the SP generates PO’s pseudonym as PPO=h1(RIDPO), where h1:Zp→Zp is a hash function. Second, the SP computes a1⋯an=h2(PPO) and takes the algebraic signature SKPO=∑x=1n‍axskpoxmodp as the PO’s private key, where h2:Zp→{0,1}n is a hash function, and a1,…,an∈{0,1}.{
P
T
D
,
S
K
T
D
}
←
R
e
g
T
D
(
R
I
D
T
D
,
S
K
S
P
,
P
K
S
P
). The SP runs this algorithm for generating a pseudonym and a private key for the TD as follows. First, the SP generates TD’s pseudonym as PTD=h1(RIDTD), where h1:Zp→Zp is a hash function. Second, the SP computes b1⋯bn=h2(PTD) and takes the algebraic signature SKTD=∑x=1n‍bxsktdxmodp as the TD’s private key, where h2:Zp→{0,1}n is a hash function, and b1,…,bn∈{0,1}.σ
R
I
←
S
i
g
n
R
I
(
R
I
,
S
K
R
I
). The PO runs this algorithm for generating a signature for the rental information as σRI=h1(RI∣SKRI), where h1:Zp→Zp is a hash function.{
σ
N
}
←
S
i
g
n
N
(
N
,
P
P
O
,
P
K
S
P
,
S
K
T
D
). The TD runs this algorithm for generating a signature for the nonce as follows. First, the TD computes PKPO=∏x=1n‍pkpoxax∈G, where a1⋯an=h2(PPO). Second, the TD computes σN=h1(N∣H(PKPOSKTD)), where h2:Zp→{0,1}n, H:G→Zp, and h1:Zp→Zp are hash functions.{
T
,
F
}
←
V
e
r
N
(
N
,
σ
N
,
S
K
P
O
,
P
T
D
,
P
K
S
P
). The PO runs this algorithm for authenticating the TD as follows. First, the PO computes PKTD=∏x=1n‍pktdxbx∈G, where b1⋯bn=h2(PTD). Second, the PO computes σN′=h1(N∣H(PKTDSKPO)) and checks σN′=?σN. If this equation holds, PO returns T. Otherwise, it returns F.{
s
k
}
←
K
e
y
g
e
n
P
O
(
N
,
S
K
P
O
,
P
T
D
,
P
K
S
P
). The PO runs this algorithm for generating the shared key as follows. First, the PO computes PKTD=∏x=1n‍pktdxbx∈G, where b1⋯bn=h2(PTD), PTD is the pseudonym of TD, and pktdx∈PKSP(x∈{1,…,n}) are distributed from the SP during the initialization phase. Second, the PO computes sk=PKTDSKPON∈G.{
τ
}
←
S
e
n
c
k
(
P
K
S
P
,
s
k
,
S
K
R
I
). The PO runs this algorithm for signing and encrypting SKRI as follows. First, the PO encrypts SKRI as c1=H(sk)⊕SKRImodp, where H:G→Zp is a hash function. Second, the PO signs SKRI as c2=h1(SKRI∣H(sk)), where H:G→Zp and h1:Zp→Zp are hash functions. Finally, the PO gets τ=(c1,c2).{
s
k
}
←
K
e
y
g
e
n
T
D
(
N
,
S
K
T
D
,
P
P
O
,
P
K
S
P
). The TD runs this algorithm for generating the shared key as follows. First, the TD computes PKPO=∏x=1n‍pkpoxax∈G, where a1⋯an=h2(PPO), PPO is the pseudonym of PO, and pkpox∈PKSP(x∈{1,…,n}) are distributed from the SP during the initialization phase. Second, the TD computes sk=PKPOSKTDN∈G.{
S
K
R
I
,
{
T
,
F
}
}
←
V
d
e
c
k
(
τ
,
s
k
,
P
K
S
P
). The TD runs this algorithm for decrypting and verifying the publishing key as follows. First, the TD decrypts SKRI as SKRI=c1⊕H(sk)modp, where H:G→Zp is a hash function. Second, the TD computes c2′=h1(SKRI∣H(sk)) and checks c2′=?c2, where H:G→Zp and h1:Zp→Zp are hash functions. If c2′=c2, the TD returns (SKRI,T). Otherwise, it returns F.{
T
,
F
}
←
V
e
r
R
I
(
R
I
,
σ
R
I
,
S
K
R
I
,
P
K
S
P
). The TD runs this algorithm for verifying the rental information as follows. First, the TD computes σRI′=h1(RI∣SKRI), where h1:Zp→Zp is a hash function. Second, the TD checks σRI′=?σRI. If this equation holds, TD returns T. Otherwise, it returns F.From this construction, it can be seen that SCPR does not use bilinear map. In fact, it employs only a few modular exponentiations, which is quite efficient. We will further evaluate the efficiency of SCPR in Section5. Note that, when computing PKPO and PKTD, there is no modular exponentiation, because ax∈{0,1} and bx∈{0,1}. So our construction is highly efficient.


## 4. Security Analysis

In this section, we show that SCPR can fulfill the security requirements described in Section1 (i.e., user privacy, key agreement, integrity of rental information, and authentication).


### 4.1. User Privacy

In SCPR, as the PO and the TD use pseudonyms generated from their real identities such as user name or driver license, this requirement is to ensure that the adversary cannot extract real identities from pseudonyms. From Section3.3, it can be seen that the SP generates pseudonyms using a one-way hash function (see equations PPO=h1(RIDPO) and PTD=h1(RIDTD) in the RegPO and RegTD algorithms for details). So it is straightforward that the adversary cannot extract RIDPO and RIDTD from PPO and PTD, and SCPR can provide user privacy protection for the PO and the TD.


### 4.2. Key Agreement

In Section3.3, the PO generates sk as sk=PKTDSKPON=(gSKTD)SKPON=gSKTDSKPON, and the TD generates sk as sk=PKPOSKTDN=(gSKPO)SKTDN=gSKTDSKPON (see the KeygenPO and KeygenTD algorithms in Section 3.3 for details.). So if the PO and the TD run SCPR correctly, they both can get sk=gSKTDSKPON.Then, we show that a potential adversary cannot extractsk in three steps. In Step  1, we describe a well-known mathematical problem that will not be efficiently solved. In Step  2, we describe the adversary. In Step  3, we show this potential adversary will not be able to extract sk efficiently. Otherwise, we will be able to use this adversary for solving the mathematical problem. So if this mathematical problem holds, the potential adversary does not exist. Our proof is described below.Step 1 (the(t,ϵ)-CDH problem [32]).
Giveng,ga,gb∈G, where a∈Zp and b∈Zp are randomly distributed unknown numbers, there is no t-time algorithm, which has the nonnegligible probability ϵ in computing gab∈G.Step 2 (the adversary).
In the parking reservation system, the potential adversary is between the PO and the TD. It can compute public keys of the PO and the TD from pseudonyms:PKPO=gSKPO=∏x=1n‍pkpoxax and PKTD=gSKTD=∏x=1n‍pktdxbx, where a1⋯an=h2(PPO) and b1⋯bn=h2(PTD). Moreover, the adversary can get N.Step 3 (the proof).
If this adversary can computesk=gSKTDSKPON from N, PKPO=gSKPO=∏x=1n‍pkpoxax, and PKTD=gSKTD=∏x=1n‍pktdxbx with the probability ϵ in time t, we can run this potential adversary with the set of parameters (PKPO=ga,PKTD=gb,N) to get sk=gSKPOSKTDN=gabN⇒gab=skN-1. That is to say, we can use this potential adversary for solving the CDH problem [32] in time t with the probability ϵ. As the CDH problem holds, this adversary does not exist. So the adversary cannot extract sk in SCPR.Finally, we show that a potential adversary cannot tampersk. Since sk is generated from N, PPO, and PTD, to tamper sk, the adversary has to tamper the pseudonyms or the nonce. The detailed proof can be illustrated in three steps too. Here, we just give a summarized example: If the adversary can tamper N to M≠N while still passing the VerN algorithm, it must be able to compute the signature σM=h1(M∣H(PKPOSKTD))=h1(M∣H(gSKPOSKTD)). Then, to compute σM, the adversary must be able to compute gSKPOSKTD. As discussed above, since the adversary cannot compute gSKPOSKTD from PKPO=gSKPO=∏x=1n‍pkpoxax and PKTD=gSKTD=∏x=1n‍pktdxbx, it cannot tamper N to M≠N.


### 4.3. Integrity of Rental Information

In SCPR, as the rental information is signed using the symmetric keySKRI, this requirement is to ensure that the adversary cannot tamper SKRI transmitted in the authentication and key agreement phase. Moreover, from the Senck and Vdeck algorithms illustrated in Section 3.3, we can see that SKRI is signed and encrypted using the negotiated shared key sk. So the integrity of rental information is to ensure that sk is secure. Since sk is secure as discussed in Section 4.2, SCPR can provide integrity protection for rental information.


### 4.4. Authentication

In SCPR, as the PO and the TD communicate with each other using pseudonyms, authentication is to make sure that the pseudonyms are generated by the SP. Moreover, asSKPO and SKTD are algebraic signatures of pseudonyms (see the equations SKPO=∑x=1n‍axskpoxmodp, skTD=∑x=1n‍bxsktdxmodp, a1⋯an=h2(PPO) and b1⋯bn=h2(PTD) in the RegPO and RegTD algorithms illustrated in Section 3.3 for details.), authentication is to prove that the PO and the TD really hold SKPO and SKTD, respectively.The proof of authentication is similar to that in Section4.2, as illustrated by the following example. In the SignN and VerN algorithms, only when the PO and the TD hold the algebraic signatures (i.e., SKPO and SKTD), they can compute PKPOSKTD=PKTDSKPO=gSKPOSKTD. Therefore, the authentication can be reduced to the CDH problem too.


## 4.1. User Privacy

In SCPR, as the PO and the TD use pseudonyms generated from their real identities such as user name or driver license, this requirement is to ensure that the adversary cannot extract real identities from pseudonyms. From Section3.3, it can be seen that the SP generates pseudonyms using a one-way hash function (see equations PPO=h1(RIDPO) and PTD=h1(RIDTD) in the RegPO and RegTD algorithms for details). So it is straightforward that the adversary cannot extract RIDPO and RIDTD from PPO and PTD, and SCPR can provide user privacy protection for the PO and the TD.


## 4.2. Key Agreement

In Section3.3, the PO generates sk as sk=PKTDSKPON=(gSKTD)SKPON=gSKTDSKPON, and the TD generates sk as sk=PKPOSKTDN=(gSKPO)SKTDN=gSKTDSKPON (see the KeygenPO and KeygenTD algorithms in Section 3.3 for details.). So if the PO and the TD run SCPR correctly, they both can get sk=gSKTDSKPON.Then, we show that a potential adversary cannot extractsk in three steps. In Step  1, we describe a well-known mathematical problem that will not be efficiently solved. In Step  2, we describe the adversary. In Step  3, we show this potential adversary will not be able to extract sk efficiently. Otherwise, we will be able to use this adversary for solving the mathematical problem. So if this mathematical problem holds, the potential adversary does not exist. Our proof is described below.Step 1 (the(t,ϵ)-CDH problem [32]).
Giveng,ga,gb∈G, where a∈Zp and b∈Zp are randomly distributed unknown numbers, there is no t-time algorithm, which has the nonnegligible probability ϵ in computing gab∈G.Step 2 (the adversary).
In the parking reservation system, the potential adversary is between the PO and the TD. It can compute public keys of the PO and the TD from pseudonyms:PKPO=gSKPO=∏x=1n‍pkpoxax and PKTD=gSKTD=∏x=1n‍pktdxbx, where a1⋯an=h2(PPO) and b1⋯bn=h2(PTD). Moreover, the adversary can get N.Step 3 (the proof).
If this adversary can computesk=gSKTDSKPON from N, PKPO=gSKPO=∏x=1n‍pkpoxax, and PKTD=gSKTD=∏x=1n‍pktdxbx with the probability ϵ in time t, we can run this potential adversary with the set of parameters (PKPO=ga,PKTD=gb,N) to get sk=gSKPOSKTDN=gabN⇒gab=skN-1. That is to say, we can use this potential adversary for solving the CDH problem [32] in time t with the probability ϵ. As the CDH problem holds, this adversary does not exist. So the adversary cannot extract sk in SCPR.Finally, we show that a potential adversary cannot tampersk. Since sk is generated from N, PPO, and PTD, to tamper sk, the adversary has to tamper the pseudonyms or the nonce. The detailed proof can be illustrated in three steps too. Here, we just give a summarized example: If the adversary can tamper N to M≠N while still passing the VerN algorithm, it must be able to compute the signature σM=h1(M∣H(PKPOSKTD))=h1(M∣H(gSKPOSKTD)). Then, to compute σM, the adversary must be able to compute gSKPOSKTD. As discussed above, since the adversary cannot compute gSKPOSKTD from PKPO=gSKPO=∏x=1n‍pkpoxax and PKTD=gSKTD=∏x=1n‍pktdxbx, it cannot tamper N to M≠N.


## 4.3. Integrity of Rental Information

In SCPR, as the rental information is signed using the symmetric keySKRI, this requirement is to ensure that the adversary cannot tamper SKRI transmitted in the authentication and key agreement phase. Moreover, from the Senck and Vdeck algorithms illustrated in Section 3.3, we can see that SKRI is signed and encrypted using the negotiated shared key sk. So the integrity of rental information is to ensure that sk is secure. Since sk is secure as discussed in Section 4.2, SCPR can provide integrity protection for rental information.


## 4.4. Authentication

In SCPR, as the PO and the TD communicate with each other using pseudonyms, authentication is to make sure that the pseudonyms are generated by the SP. Moreover, asSKPO and SKTD are algebraic signatures of pseudonyms (see the equations SKPO=∑x=1n‍axskpoxmodp, skTD=∑x=1n‍bxsktdxmodp, a1⋯an=h2(PPO) and b1⋯bn=h2(PTD) in the RegPO and RegTD algorithms illustrated in Section 3.3 for details.), authentication is to prove that the PO and the TD really hold SKPO and SKTD, respectively.The proof of authentication is similar to that in Section4.2, as illustrated by the following example. In the SignN and VerN algorithms, only when the PO and the TD hold the algebraic signatures (i.e., SKPO and SKTD), they can compute PKPOSKTD=PKTDSKPO=gSKPOSKTD. Therefore, the authentication can be reduced to the CDH problem too.


## 5. Efficiency Evaluation

There are many crowdsourcing-based systems (i.e., [5–30]). But, only [5, 6] aimed to design complete cryptographic algorithms and protocols [4], while other systems mainly focused on deploying crowdsourcing-based systems in multiple real world applications. So, in this section, we mainly compare SCPR with [5, 6].Time cost is the major efficiency issue for parking reservation systems, which is comprised of computation and communication costs as discussed in Section1. So we will first compare the computation cost of SCPR with those of [5, 6] in Section 5.1. Then, we shall compare the communication costs in Section 5.2. Finally, in Section 5.3, we will show the implementation of SCPR to make sure the newly designed protocol works well.


### 5.1. Comparison of Computation Costs

Computation cost is the major measure of time cost, which is mainly consumed by cryptographic algorithms. So we first tested computation costs of basic cryptographic algorithms. Then, we computed the computation costs of SCPR [5, 6].To investigate the computation costs of basic cryptographic algorithms, we conducted the experiment on a computer with a CENTOS operating system and an Intel i7 processor. Cryptographic libraries used in this experiment include OPENSSL [33] and PBC [34]. Cryptographic group (i.e., G in Section 3) used in this experiment is the 160-bit elliptic curve [33]. Finally, we used the SHA1 hash function [33] and type F bilinear pairing parameter [34] in this experiment.Table1 lists the computation costs of basic cryptographic algorithms, in which the values are means of running basic cryptographic algorithms for 10,000 times. From Table 1, we can see the following.Table 1
Basic algorithms (unit:μs).
T
m
m
T
h
T
p
T
m
e
0.1
0.5
29540.2
577.8
T
m
m: computation cost of modular multiplication, Th: computation cost of hash function, Tp: computation cost of bilinear pairing, and Tme: computation cost of modular exponentiation.(
1
) The computation costs of modular multiplication and hash function are much lower than those of modular exponentiation and bilinear pairing and can be omitted. This is because Th/Tp=0.5/29540.2≈1.7×10-5, Th/Tme=0.5/577.8≈8.7×10-4, and Th/Tmm=0.5/0.1=5. Therefore, in the following evaluation, we only take modular exponentiation and bilinear pairing into account.(
2
) The computation cost of modular exponentiation is much lower than that of bilinear pairing. This is because Tme/Tp=577.8/29540.2≈2.0×10-2. Therefore, by avoiding using bilinear pairing, SCPR can reduce the computation cost significantly.Then, from Table1, we computed the total computation costs of SCPR [5, 6]. The results are shown in Table 2 and Figure 2, where the values are total computation costs of modular exponentiation and bilinear pairing executed during the publishing phase and the authentication and key agreement phase. From Table 2 and Figure 2, we can see the following.Table 2
Comparison of computation costs (unit:ms).
SCPR
[5]
[6]
TPO
2
T
m
e
=
1.2
T
p
+
T
m
e
=
30.1
n
(
T
p
+
4
T
m
e
)
+
5
T
m
e
=
31.9
n
+
2.9
TTD
2
T
m
e
=
1.2
4
T
p
=
118.2
(
3
T
p
+
T
m
e
)
n
2
+
2
n
T
p
=
89.2
n
2
+
59.1
n
Ta
4
T
m
e
=
2.3
5
T
p
+
T
m
e
=
148.3
(
3
T
p
+
T
m
e
)
n
2
+
n
(
3
T
p
+
4
T
m
e
)
+
5
T
m
e
=
89.2
n
2
+
91
n
+
2.9
T
P
O: computation cost of the PO, TTD: computation cost of the TD, Ta: total computation cost on both the PO and the TD, and n: number of attributes in [5, 6].Figure 2
Evolution of computation costs.(
1
) On the PO’s side, the computation costs of [5, 6] are around 101 to that of SCPR. This is because (31.9n+2.9)/1.2>(31.9×1+2.9)/1.2≈2.9×101 and 30.1/1.2≈2.5×101.(
2
) On the TD’s side, the computation costs of [5, 6] are around 101~102 to that of SCPR. This is because (89.2n2+59.1n)/1.2>(89.2+59.1)/1.2≈1.2×102 and 118.2/1.2≈9.9×101.(
3
) The total computation costs of [5, 6] are around 101 to that of SCPR. This is because (89.2n2+91n+2.9)/2.3>(89.2+91+2.9)/2.3≈8.0×101 and 148.3/2.3≈6.4×101.(
4
) On the TD’s side, the computation cost of [6] will increase rapidly, when the number of attributes increases, as shown in Figure 2.These three conclusions show that the computation cost of SCPR is much lower than those of [5, 6]. So SCPR can fulfill requirement (5) listed in Section 1.


### 5.2. Comparison of Communication Costs

During the publishing phase, the number of messages is one in SCPR [5, 6]. During the authentication and key agreement phase, both SCPR and [6] contain two messages, while [5] contains four messages. That is to say, SCPR and [6] contain fewer messages than [5]. So SCPR can fulfill requirement (5) listed in Section 1.


### 5.3. Implementation of SCPR

To make sure SCPR can work well, we implemented it. In the experiment, we use three computers, acting as the SP, the PO, and the TD, respectively. These three computers communicate with each other using1Gbps Ethernet. All the three computers have Intel i7 CPUs and are installed with CENTOS operating system. The cryptographic libraries used in the experiment are OPENSSL and PBC [33, 34] with the same parameters as those in Section 5.1. The Language used in our experiment is C, and the protocol for transmitting SCPR messages is TCP. Then, we get the total executing time of SCPR ≈2.4ms. This is similar to the value computed in Table 2. Therefore, time cost is mainly consumed by cryptographic algorithms, and SCPR is feasible for real world applications.


## 5.1. Comparison of Computation Costs

Computation cost is the major measure of time cost, which is mainly consumed by cryptographic algorithms. So we first tested computation costs of basic cryptographic algorithms. Then, we computed the computation costs of SCPR [5, 6].To investigate the computation costs of basic cryptographic algorithms, we conducted the experiment on a computer with a CENTOS operating system and an Intel i7 processor. Cryptographic libraries used in this experiment include OPENSSL [33] and PBC [34]. Cryptographic group (i.e., G in Section 3) used in this experiment is the 160-bit elliptic curve [33]. Finally, we used the SHA1 hash function [33] and type F bilinear pairing parameter [34] in this experiment.Table1 lists the computation costs of basic cryptographic algorithms, in which the values are means of running basic cryptographic algorithms for 10,000 times. From Table 1, we can see the following.Table 1
Basic algorithms (unit:μs).
T
m
m
T
h
T
p
T
m
e
0.1
0.5
29540.2
577.8
T
m
m: computation cost of modular multiplication, Th: computation cost of hash function, Tp: computation cost of bilinear pairing, and Tme: computation cost of modular exponentiation.(
1
) The computation costs of modular multiplication and hash function are much lower than those of modular exponentiation and bilinear pairing and can be omitted. This is because Th/Tp=0.5/29540.2≈1.7×10-5, Th/Tme=0.5/577.8≈8.7×10-4, and Th/Tmm=0.5/0.1=5. Therefore, in the following evaluation, we only take modular exponentiation and bilinear pairing into account.(
2
) The computation cost of modular exponentiation is much lower than that of bilinear pairing. This is because Tme/Tp=577.8/29540.2≈2.0×10-2. Therefore, by avoiding using bilinear pairing, SCPR can reduce the computation cost significantly.Then, from Table1, we computed the total computation costs of SCPR [5, 6]. The results are shown in Table 2 and Figure 2, where the values are total computation costs of modular exponentiation and bilinear pairing executed during the publishing phase and the authentication and key agreement phase. From Table 2 and Figure 2, we can see the following.Table 2
Comparison of computation costs (unit:ms).
SCPR
[5]
[6]
TPO
2
T
m
e
=
1.2
T
p
+
T
m
e
=
30.1
n
(
T
p
+
4
T
m
e
)
+
5
T
m
e
=
31.9
n
+
2.9
TTD
2
T
m
e
=
1.2
4
T
p
=
118.2
(
3
T
p
+
T
m
e
)
n
2
+
2
n
T
p
=
89.2
n
2
+
59.1
n
Ta
4
T
m
e
=
2.3
5
T
p
+
T
m
e
=
148.3
(
3
T
p
+
T
m
e
)
n
2
+
n
(
3
T
p
+
4
T
m
e
)
+
5
T
m
e
=
89.2
n
2
+
91
n
+
2.9
T
P
O: computation cost of the PO, TTD: computation cost of the TD, Ta: total computation cost on both the PO and the TD, and n: number of attributes in [5, 6].Figure 2
Evolution of computation costs.(
1
) On the PO’s side, the computation costs of [5, 6] are around 101 to that of SCPR. This is because (31.9n+2.9)/1.2>(31.9×1+2.9)/1.2≈2.9×101 and 30.1/1.2≈2.5×101.(
2
) On the TD’s side, the computation costs of [5, 6] are around 101~102 to that of SCPR. This is because (89.2n2+59.1n)/1.2>(89.2+59.1)/1.2≈1.2×102 and 118.2/1.2≈9.9×101.(
3
) The total computation costs of [5, 6] are around 101 to that of SCPR. This is because (89.2n2+91n+2.9)/2.3>(89.2+91+2.9)/2.3≈8.0×101 and 148.3/2.3≈6.4×101.(
4
) On the TD’s side, the computation cost of [6] will increase rapidly, when the number of attributes increases, as shown in Figure 2.These three conclusions show that the computation cost of SCPR is much lower than those of [5, 6]. So SCPR can fulfill requirement (5) listed in Section 1.


## 5.2. Comparison of Communication Costs

During the publishing phase, the number of messages is one in SCPR [5, 6]. During the authentication and key agreement phase, both SCPR and [6] contain two messages, while [5] contains four messages. That is to say, SCPR and [6] contain fewer messages than [5]. So SCPR can fulfill requirement (5) listed in Section 1.


## 5.3. Implementation of SCPR

To make sure SCPR can work well, we implemented it. In the experiment, we use three computers, acting as the SP, the PO, and the TD, respectively. These three computers communicate with each other using1Gbps Ethernet. All the three computers have Intel i7 CPUs and are installed with CENTOS operating system. The cryptographic libraries used in the experiment are OPENSSL and PBC [33, 34] with the same parameters as those in Section 5.1. The Language used in our experiment is C, and the protocol for transmitting SCPR messages is TCP. Then, we get the total executing time of SCPR ≈2.4ms. This is similar to the value computed in Table 2. Therefore, time cost is mainly consumed by cryptographic algorithms, and SCPR is feasible for real world applications.


## 6. Conclusion

In this paper, we have presented a security protocol for crowdsourcing-based parking reservation systems called SCPR. It can satisfy many security requirements that have not been addressed by current protocols, such as user privacy and key agreement. More importantly, to reduce the time cost, we designed several novel cryptographic algorithms for SCPR, which are quite light weight. Experimental results show SCPR is feasible for real world applications.However, there are several more problems remaining to be solved. First, after the transaction is ended, the tenant driver and the private owner should be able to score the transaction. By doing so, the parking reservation system can provide differential services to users based on their reputation. Second, SCPR lacks a revocation method. These open issues are to be addressed in the future.



---

*Source: 1076419-2017-05-28.xml*