# A Mobile, Dynamic, and Privacy-Preserving Matching System for Car and Taxi Pools

Authors: Shin-Yan Chiou; Yi-Cheng Chen
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Recently, rates of vehicle ownership have risen globally, exacerbating problems including air pollution, lack of parking, and traffic congestion. While many solutions to these problems have been proposed, carpooling remains one of the most effective approaches. Recently, several carpooling platforms have been built on cloud computing systems, with originators posting online list of departure/arrival points and schedules from which participants can search for rides that match their needs. However, it can be difficult to make matches quickly and the systems are subject to privacy concerns in that they may disclose private information such as names, registration data, and departure/arrival schedules. This paper proposes a dynamic matching method for car/taxi pools for use in mobile devices via ad hoc Wi-Fi networks. The proposed method also preserves user privacy including names and departure/arrival schedules. Moreover, the system does not require the user to register any personal data, so such data cannot be leaked. The system was implemented on the Android mobile platform, allowing users to immediately and securely access the system via their smart phones.


---

## Body

## 1. Introduction

In recent years, car ownership has exploded globally, exacerbating the negative side effects of driving, including depletion of fossil fuels and the production of carbon dioxide and other emissions; thus driving accelerates the development of air pollution, acid rain, and climate change. In addition, increased car ownership has increased traffic congestion [1–4], strained the availability of existing parking facilities [5–12], and reduced economic performance [13]. Scholars have proposed many solutions to these issues, including carpooling [14–20], which remains one of the most effective solutions.In 1983 Fagin and Williams [14] first proposed a sharing mechanism, while other scholars [15–18] have also proposed various carpooling methods. In these methods, group members take turns serving as drivers. However, this approach is difficult to promote or apply widely because it only works if group members already know each other and agree ahead of time to organize a carpool.In recent years, increases to network speeds have prompted scholars [19, 20] to propose the establishment of networked platforms [21–29] as a mechanism for organizing carpools. Di Martino et al. [19] proposed the Lift4U platform, a carpool matching algorithm based on cloud and positioning systems. The platform uses Bing Maps and GPS modules to provide access to car sharing, bike sharing, and public transport on mobile platforms. Lalos et al. [20] also describe a dynamic framework for car and taxi pool services through the use of positioning systems on mobile devices to determine the location of carpool members. These positions are then shown directly on the mobile device interface, helping carpool drivers to arrange pickups.These systems use Internet and cloud computing technologies [30] to provide access to information required to participate in carpooling schemes; thus group members need not know each other or organize the carpool ahead of time. However, initiating a carpool or finding carpool originators entails a process of online registration, login, search, and comparison, thus producing a match between rider demand and driver availability. Therefore, in addition to being ineffective in helping carpoolers to coordinate in real time, these methods require originators to expose their personal information including name, location, destination, driving time, and expose participants’ personal information including name and telephone number.This paper proposes a carpooling matching method deployed on mobile devices, wherein users can instantly initiate or participate in carpools via smartphones or tablet PCs via ad hoc Wi-Fi networks. The proposed method also protects user privacy, using a private matching method [31, 32] to protect the privacy of participants on both sides of the transaction, including name, origin, destination, and driving time.The proposed system was implemented on Android smartphones, allowing users to directly, immediately, and securely find carpoolers. The implementation can be used directly to find rides from private carpools or taxi pools. For example, imagine a group of strangers emerging from a subway station and arriving at the adjacent bus stop immediately after their intended bus had pulled away, leaving them to wait another 20 minutes for the next bus. These individuals can access the proposed system via their smartphones to arrange for a taxi pool, thus saving time and money, while protecting their personal information.The remainder of this paper is organized as follows. Section2 discusses security issues and solutions for the proposed method and describes the research methods. Section 3 describes the proposed method, while Section 4 presents the analysis methods used, including accuracy analysis, locational error, and security analysis, and provides a comparison with other related methods. Section 5 introduces the implementation of the proposed system on Android phones and the final section presents concluding remarks.


## 2. Related Work

Most research into carpooling focuses on scheduling algorithms and matching algorithms, which are briefly introduced here.


### 2.1. Carpool Scheduling Algorithms

Fagin and Williams [14] and others [15–18] have proposed fair carpool scheduling algorithms wherein the participants take turns to drive the rest of the group. Here, we introduce four approaches including simple rotation, simple tokens, subsets, and fair carpool. Among these, simple rotation has a fixed set of N members, where person i is responsible for driving on the ith day and every N driving days. This approach is simple to describe and it is easy to determine who drives next. However, inconsistencies (e.g., if a driver cannot drive and has to swap days) can disrupt the schedule and make it difficult to determine who drives next.In the simple tokens approach, a participantP pays a driver D one “ride token” each time P rides with D. The person with the fewest tokens would be the next driver. However, external conditions may render the designated driver unable to drive on a given day without warning.In the subset approach, each of the2
N
-
(
N
+
1
) subsets of carpool members for N persons can drive particular groups. Drivers get “subset ride tokens” from that subset to determine who drives next. However, this approach is very complex given the large number of subsets.In fair carpool [14], each participant pays U
/
k tokens to the driver in each carpool, where U is a constant value and k is the number of participants in each carpool time. However, this approach is unbalanced.


### 2.2. Carpooling Matching Algorithm

Many studies have proposed carpooling matching algorithms. Here, we review Di Martino et al.’s Lift4U platform [19], which uses Bing Maps and GPS modules to provide a range of carpooling applications (see Figure 1(a)). This method includes registration and data matching phases as follows.Lift4U system.
(a)
The framework of Lift4U
(b)
Set the search radius to find others with the same destination
(c)
Plot potential routes
(d)
Select carpoolers(
1) Registration Phase. In this stage, the user registers online. The user’s identity is confirmed, using information including the user’s name, gender, date of birth, and telephone number.(
2) Data, Matching Phase. This stage includes four steps through which the user is matched with a ride.Step 1.
The user accesses Bing Maps to establish points of departure and destination.Step 2.
The user sets a search radius around the departure point to search for other people seeking the same destination (see Figure1(b)).Step 3.
The user finds other potential carpoolers within the search area (see Figure1(c)), plots routes, and calculates the distances.Step 4.
The user determines the shortest route and invites potential carpoolers to join based on which pickups result in the shortest route (see Figure1(d)).


## 2.1. Carpool Scheduling Algorithms

Fagin and Williams [14] and others [15–18] have proposed fair carpool scheduling algorithms wherein the participants take turns to drive the rest of the group. Here, we introduce four approaches including simple rotation, simple tokens, subsets, and fair carpool. Among these, simple rotation has a fixed set of N members, where person i is responsible for driving on the ith day and every N driving days. This approach is simple to describe and it is easy to determine who drives next. However, inconsistencies (e.g., if a driver cannot drive and has to swap days) can disrupt the schedule and make it difficult to determine who drives next.In the simple tokens approach, a participantP pays a driver D one “ride token” each time P rides with D. The person with the fewest tokens would be the next driver. However, external conditions may render the designated driver unable to drive on a given day without warning.In the subset approach, each of the2
N
-
(
N
+
1
) subsets of carpool members for N persons can drive particular groups. Drivers get “subset ride tokens” from that subset to determine who drives next. However, this approach is very complex given the large number of subsets.In fair carpool [14], each participant pays U
/
k tokens to the driver in each carpool, where U is a constant value and k is the number of participants in each carpool time. However, this approach is unbalanced.


## 2.2. Carpooling Matching Algorithm

Many studies have proposed carpooling matching algorithms. Here, we review Di Martino et al.’s Lift4U platform [19], which uses Bing Maps and GPS modules to provide a range of carpooling applications (see Figure 1(a)). This method includes registration and data matching phases as follows.Lift4U system.
(a)
The framework of Lift4U
(b)
Set the search radius to find others with the same destination
(c)
Plot potential routes
(d)
Select carpoolers(
1) Registration Phase. In this stage, the user registers online. The user’s identity is confirmed, using information including the user’s name, gender, date of birth, and telephone number.(
2) Data, Matching Phase. This stage includes four steps through which the user is matched with a ride.Step 1.
The user accesses Bing Maps to establish points of departure and destination.Step 2.
The user sets a search radius around the departure point to search for other people seeking the same destination (see Figure1(b)).Step 3.
The user finds other potential carpoolers within the search area (see Figure1(c)), plots routes, and calculates the distances.Step 4.
The user determines the shortest route and invites potential carpoolers to join based on which pickups result in the shortest route (see Figure1(d)).


## 3. Proposed Scheme

We use the error-tolerable private matching to achieve private carpool matching. This method not only allows the user to directly use mobile devices to find potential carpoolers with similar points of origin and destinations in real time but also allows the user to expand the search range using a quantifier, for which the quantification space can be autonomously selected (see Figure2), thus finding more potential carpoolers.Figure 2
Carpooling schematic.This paper uses the symbols listed in Notations Section, whereQ
(
x
,
y
) represents x quantized as x
(
q
)
∈
{
i
p
∣
i
=
0
,
1
,
2
,
…
,
p
=
2
y
} s.t. -
y
<
x
(
q
)
-
x
≤
y. Map(
·
) is the transformed longitude and latitude function. For example, Map(
x
) represents the transformed longitude and latitude for map message x. Using Google Maps, the map message Ds
t
A is thus transformed into the longitude and latitude message L
L
A, and L
L
A
=
Map
(
Ds
t
A
).Figures3 and 4 illustrate the operation process (using a taxi pool as an example). Figure 3 provides a detailed flow chart of the system operations, providing a detailed understanding or point of reference for programmers. Figure 4 provides a simplified schematic flow diagram for the system. In this system, “originator” is the car owner inviting others to join a carpool or is an initial taxi passenger inviting others to share the ride, and “participant” is a person who wants to join a car or taxi pool. The process goes through the following steps.Figure 3
System programming flow chart.Figure 4
System flow diagram.Step 1.
A user can either select “Listen” to determine whether someone has already initiated the carpool matching service (go to Step2) or directly acts as the originator of a car or taxi pool (go to Step 3).Step 2.
After Listening, if the user receives a “Taxipool” or “Carpool” message, he/she can then elect to act as participant or originator. Otherwise if a “Taxipool” or “Carpool” message is not received and the participant option is not available, the user can still elect to act as originator, or return to Step1.Step 3.
If the user elects to act as originator, an appropriate (i.e., “Carpool” or “Taxipool”) message is broadcast.Step 4.
If the user elects to act as participant, once he/she receives a “Taxipool” or “Carpool” message, he/she agrees to the match by sending a “GoMatch” message to the originator. Otherwise, go to Step1.Step 5.
The originator receives the “GoMatch” message and inputs his/her own destinationDs
t
A and search range Rng
A. He/she computes L
L
A
=
Map
(
Ds
t
A
), which uses Map
(
·
) to transform Ds
t
A into the latitude and longitude message L
L
A and uses the quantizer to calculate L
L
A
(
q
)
=
Q
(
LL
A
,
Rng
A
), thus using LL
A to obtain the quantized L
L
A
(
q
). He/she then uses the adjustment function to calculate Adj
A
=
LL
A
-
L
L
A
(
q
). Finally he/she transmits Adj
A and Rng
A to the participant.Step 6.
The participant inputs his/her own destinationDs
t
B and calculates LL
B
=
Map
(
Dst
B
). After receiving Adj
A and Rng
A from the originator, the participant uses the adjustment function to calculate LL
B
′
=
LL
B
-
Adj
A and then computes LL
B
′
(
q
)
=
Q
(
LL
B
′
,
Rng
A
). Finally, the participant calculates h
B
=
H
(
LL
B
′
(
q
)
)and transmits h
B back to the originator.Step 7.
After the originator receivesh
B, he/she calculates H
(
L
L
A
(
q
)
) and determines whether it matches h
B. If it matches, he/she transmits an “OK” message to the participant.Step 8.
Finally, when the participant receives the “OK” message, he/she begins to negotiate the taxi pool or carpool arrangement with the originator.


## 4. System Analysis and Comparison

### 4.1. Match Correctness

In this system, matching will only succeed if the distance betweenDst
A and Ds
t
B falls within Rng
A. That is to say matching is only successful when
(1)
-
Rn
g
A
<
L
L
A
-
L
L
B
≤
Rn
g
A
.Theorem 1.
In this system, if-
R
n
g
A
<
L
L
A
-
L
L
B
≤
R
n
g
A, matching will be successful.Proof.
SinceAdj
A
=
LL
A
-
L
L
A
(
q
) and LL
B
′
=
LL
B
-
Adj
A, we have
(2)
L
L
A
-
LL
B
=
L
L
A
(
q
)
-
LL
B
′
.
From the assumption -
Rng
A
<
LL
A
-
LL
B
≤
Rng
A, we get
(3)
-
Rng
A
<
L
L
A
(
q
)
-
LL
B
′
≤
Rng
A
.
Also from the definition of Q
(
x
,
y
), we know that -
Rng
A
<
LL
B
′
(
q
)
-
LL
B
′
≤
Rng
A since LL
B
′
(
q
)
=
Q
(
LL
B
′
,
Rng
A
). We can get
(4)
-
Rng
A
≤
LL
B
′
-
LL
B
′
(
q
)
<
Rng
A
.
From (3) and (4), we get -
2
Rng
A
<
L
L
A
(
q
)
-
LL
B
′
(
q
)
<
2
Rng
A. Because both L
L
A
(
q
) and LL
B
′
(
q
) belong to {
i
p
∣
i
=
0,1
,
2
,
…
,
p
=
2
Rng
A
}, we can conclude that L
L
A
(
q
)
=
LL
B
′
(
q
).Conversely, if (1) does not hold, matching fails. That is, if LL
A
-
LL
B
>
Rng
A or LL
A
-
LL
B
≤
-
Rng
A, matching fails.Theorem 2.
In this system, if-
R
n
g
A
<
L
L
A
-
L
L
B
≤
R
n
g
A does not hold, matching fails.Proof.
(1) IfLL
A
-
LL
B
>
Rng
A, from (2), we get
(5)
L
L
A
(
q
)
-
LL
B
′
>
Rng
A
.
From (4), we know that
(6)
LL
B
′
-
LL
B
′
(
q
)
≥
-
Rng
A
.
From (5) and (6), we conclude that L
L
A
(
q
)
-
LL
B
′
(
q
)
>
0. Therefore, L
L
A
(
q
)
≠
LL
B
′
(
q
).
(2) IfLL
A
-
LL
B
≤
-
Rng
A, from (2), we get
(7)
L
L
A
(
q
)
-
LL
B
′
≤
-
Rng
A
.
From (4), we know that
(8)
LL
B
′
-
LL
B
′
(
q
)
<
Rng
A
.
From (7) and (8), we conclude that L
L
A
(
q
)
-
LL
B
′
(
q
)
<
0. Therefore, L
L
A
(
q
)
≠
LL
B
′
(
q
).


### 4.2. Obtaining Latitude/Longitude Values and Quantified Scopes and Regulating Pairing Errors

Google Maps features different coordinate formats and GPS modes, requiring conversion for interoperability. The conversion formula is as follows:(9)
X
degrees
Y
minutes
Z
seconds
(
GPS
mode
)
=
X
+
Y
60
+
Z
3600
(
Google
Maps
decimal
degrees
)
.Longitude and latitude have different relationships to distance. In latitude, one degree is equivalent to 111.19 km, while one degree of longitude is equivalent to 101.35 km. Therefore, an input range with an error value of 1 km can be used to obtain a quantized interval of 2 km, which is converted to approximately 2/111.19 degrees latitude and 2/101.35 degrees longitude. This produces a set of quantized values.If the quantized values for latitude and longitude are obtained, a restriction exists that the matching range can produce a square-shaped “square pairing” area, two km on each side (see Figure2), rather than a circular range with a diameter of two km for “circular pairing.” Thus, the distance from the point of departure to the four corners of the square pairing area exceeds Rng
A, but matching is successful (see red stripped ball in Figure 5(a)), while the maximal error distance is +
(
2
-
1
)
Rng
A (or the maximal distance error rate is +41.4%), and the average false acceptance rate (FAR) is 21.46% and false rejection rate (FRR) is zero. However, one can also adjust the determination method for control of maximal error distance in -
(
1
-
(
2
/
2
)
)
Rng
A (approximately −29.29% with FAR being zero and FRR being 36.34%) (see Figure 5(b)) or ±
(
3
-
2
2
)
Rng
A (approximately ±17.16% with FAR being 4.57% and FRR being 16.62%) (see Figure 5(c)). Herein, Figure 5(c) is a relatively acceptable option. That is, for the user’s input error range of 1 km (1000 m), the worst-case scenario would be (1) successful matching at a distance of 1171.5 meters (see point A in Figure 5(c)) or (2) unsuccessful matching at a distance of 828.5 meters (see point B in Figure 5(c)).Pairing error.
(a)
(b)
(c)


### 4.3. Security Analysis

When using the program, users may be concerned that others may be able to access their departure or destination point information. The proposed protocol ensures user privacy, allowing users to engage with the system without fear that their personal information may be leaked to unauthorized parties. In the proposed scheme, attackers are unable to obtain a plain text message through analyzing the transmitted information. Moreover, after finishing this protocol, neither the originator nor participant is aware of each other’s information unless they share a common destination. We analyze possible means of attack as follows.(
1) Participant Attempts to Eavesdrop on the Privacy of Originator. In the proposed protocol, the participant is only able to receive Adj
A and Rng
A messages and is unable to access private information related to the originator such as intended destination.(
2) Originator Attempts to Eavesdrop on the Privacy of Participant.In the proposed protocol, the originator is only able to receive the participant’s h
B message. If matching fails, the originator is unable to access private information related to the participant such as intended destination.(
3) Third Party Attackers Attempt to Eavesdrop on the Privacy of Originator or Participant. In the proposed protocol, although an attacker can eavesdrop on the Adj
A, Rng
A, and h
B messages, he/she is unable to access private information, such as the intended destination of either the originator or participant.Thus, if the originator and participant have different intended destinations, neither is aware of the other. In addition, if an attacker eavesdrops on these messages, the messages cannot be compromised thus preserving the privacy of both parties.In addition, if the negotiated content is subject to eavesdropping concerns, one of the following two advanced steps can be taken.(1)
The originator (in Step7) calculates S
K
A
B
=
H
(
L
L
A
(
q
)
+
1
) and the participant (in Step 8) calculates S
K
B
A
=
H
(
LL
B
′
(
q
)
+
1
), thus obtaining a secret protocol key S
K
A
B
=
S
K
B
A. This key can be used for encryption and decryption, thus allowing participants to negotiate carpool details.
(2)
After the originator receives the “GoMatch” message (in Step5), he/she can conduct a Diffie-Hellman key exchange of the key SK
A
B with the participant, and this key can then be used to encrypt the following message.


### 4.4. Comparison

Table1 presents a comparison of our proposed system with scheduling algorithms (e.g., Fagin and Williams [14]) and carpooling matching algorithms (including Lift4U [19] and Lalos et al.’s algorithm [20]). All the algorithms can provide carpool functions, while [19, 20] require GPS for the comparison. In terms of scheduling algorithms, because the system requires prior communication to coordinate matching, the users must know each other prior to using the system. In addition, because scheduling algorithms are planned ahead of time and Lift4U relies on a networked platform for matching, therefore it is unable to provide real-time, spur-of-the-moment carpooling. Most methods require prior registration or login and use networked platforms to run their matching algorithms, thus requiring Internet access. Also, most methods fail to consider privacy concerns. However, the proposed method provides all of these functions, while providing privacy protection.Table 1
Comparison.
Function
Fagin and Williams [14]
Lift4U [19]
Lalos et al. [20]
Proposed system
Carpool
v
v
v
v
Does not require GPS for matching
v
v
Users do not need to know each other
v
v
v
Spur-of-the-moment matching
v
v
Does not require registration
v
Does not require Internet access
v
v
Privacy protection
v


## 4.1. Match Correctness

In this system, matching will only succeed if the distance betweenDst
A and Ds
t
B falls within Rng
A. That is to say matching is only successful when
(1)
-
Rn
g
A
<
L
L
A
-
L
L
B
≤
Rn
g
A
.Theorem 1.
In this system, if-
R
n
g
A
<
L
L
A
-
L
L
B
≤
R
n
g
A, matching will be successful.Proof.
SinceAdj
A
=
LL
A
-
L
L
A
(
q
) and LL
B
′
=
LL
B
-
Adj
A, we have
(2)
L
L
A
-
LL
B
=
L
L
A
(
q
)
-
LL
B
′
.
From the assumption -
Rng
A
<
LL
A
-
LL
B
≤
Rng
A, we get
(3)
-
Rng
A
<
L
L
A
(
q
)
-
LL
B
′
≤
Rng
A
.
Also from the definition of Q
(
x
,
y
), we know that -
Rng
A
<
LL
B
′
(
q
)
-
LL
B
′
≤
Rng
A since LL
B
′
(
q
)
=
Q
(
LL
B
′
,
Rng
A
). We can get
(4)
-
Rng
A
≤
LL
B
′
-
LL
B
′
(
q
)
<
Rng
A
.
From (3) and (4), we get -
2
Rng
A
<
L
L
A
(
q
)
-
LL
B
′
(
q
)
<
2
Rng
A. Because both L
L
A
(
q
) and LL
B
′
(
q
) belong to {
i
p
∣
i
=
0,1
,
2
,
…
,
p
=
2
Rng
A
}, we can conclude that L
L
A
(
q
)
=
LL
B
′
(
q
).Conversely, if (1) does not hold, matching fails. That is, if LL
A
-
LL
B
>
Rng
A or LL
A
-
LL
B
≤
-
Rng
A, matching fails.Theorem 2.
In this system, if-
R
n
g
A
<
L
L
A
-
L
L
B
≤
R
n
g
A does not hold, matching fails.Proof.
(1) IfLL
A
-
LL
B
>
Rng
A, from (2), we get
(5)
L
L
A
(
q
)
-
LL
B
′
>
Rng
A
.
From (4), we know that
(6)
LL
B
′
-
LL
B
′
(
q
)
≥
-
Rng
A
.
From (5) and (6), we conclude that L
L
A
(
q
)
-
LL
B
′
(
q
)
>
0. Therefore, L
L
A
(
q
)
≠
LL
B
′
(
q
).
(2) IfLL
A
-
LL
B
≤
-
Rng
A, from (2), we get
(7)
L
L
A
(
q
)
-
LL
B
′
≤
-
Rng
A
.
From (4), we know that
(8)
LL
B
′
-
LL
B
′
(
q
)
<
Rng
A
.
From (7) and (8), we conclude that L
L
A
(
q
)
-
LL
B
′
(
q
)
<
0. Therefore, L
L
A
(
q
)
≠
LL
B
′
(
q
).


## 4.2. Obtaining Latitude/Longitude Values and Quantified Scopes and Regulating Pairing Errors

Google Maps features different coordinate formats and GPS modes, requiring conversion for interoperability. The conversion formula is as follows:(9)
X
degrees
Y
minutes
Z
seconds
(
GPS
mode
)
=
X
+
Y
60
+
Z
3600
(
Google
Maps
decimal
degrees
)
.Longitude and latitude have different relationships to distance. In latitude, one degree is equivalent to 111.19 km, while one degree of longitude is equivalent to 101.35 km. Therefore, an input range with an error value of 1 km can be used to obtain a quantized interval of 2 km, which is converted to approximately 2/111.19 degrees latitude and 2/101.35 degrees longitude. This produces a set of quantized values.If the quantized values for latitude and longitude are obtained, a restriction exists that the matching range can produce a square-shaped “square pairing” area, two km on each side (see Figure2), rather than a circular range with a diameter of two km for “circular pairing.” Thus, the distance from the point of departure to the four corners of the square pairing area exceeds Rng
A, but matching is successful (see red stripped ball in Figure 5(a)), while the maximal error distance is +
(
2
-
1
)
Rng
A (or the maximal distance error rate is +41.4%), and the average false acceptance rate (FAR) is 21.46% and false rejection rate (FRR) is zero. However, one can also adjust the determination method for control of maximal error distance in -
(
1
-
(
2
/
2
)
)
Rng
A (approximately −29.29% with FAR being zero and FRR being 36.34%) (see Figure 5(b)) or ±
(
3
-
2
2
)
Rng
A (approximately ±17.16% with FAR being 4.57% and FRR being 16.62%) (see Figure 5(c)). Herein, Figure 5(c) is a relatively acceptable option. That is, for the user’s input error range of 1 km (1000 m), the worst-case scenario would be (1) successful matching at a distance of 1171.5 meters (see point A in Figure 5(c)) or (2) unsuccessful matching at a distance of 828.5 meters (see point B in Figure 5(c)).Pairing error.
(a)
(b)
(c)


## 4.3. Security Analysis

When using the program, users may be concerned that others may be able to access their departure or destination point information. The proposed protocol ensures user privacy, allowing users to engage with the system without fear that their personal information may be leaked to unauthorized parties. In the proposed scheme, attackers are unable to obtain a plain text message through analyzing the transmitted information. Moreover, after finishing this protocol, neither the originator nor participant is aware of each other’s information unless they share a common destination. We analyze possible means of attack as follows.(
1) Participant Attempts to Eavesdrop on the Privacy of Originator. In the proposed protocol, the participant is only able to receive Adj
A and Rng
A messages and is unable to access private information related to the originator such as intended destination.(
2) Originator Attempts to Eavesdrop on the Privacy of Participant.In the proposed protocol, the originator is only able to receive the participant’s h
B message. If matching fails, the originator is unable to access private information related to the participant such as intended destination.(
3) Third Party Attackers Attempt to Eavesdrop on the Privacy of Originator or Participant. In the proposed protocol, although an attacker can eavesdrop on the Adj
A, Rng
A, and h
B messages, he/she is unable to access private information, such as the intended destination of either the originator or participant.Thus, if the originator and participant have different intended destinations, neither is aware of the other. In addition, if an attacker eavesdrops on these messages, the messages cannot be compromised thus preserving the privacy of both parties.In addition, if the negotiated content is subject to eavesdropping concerns, one of the following two advanced steps can be taken.(1)
The originator (in Step7) calculates S
K
A
B
=
H
(
L
L
A
(
q
)
+
1
) and the participant (in Step 8) calculates S
K
B
A
=
H
(
LL
B
′
(
q
)
+
1
), thus obtaining a secret protocol key S
K
A
B
=
S
K
B
A. This key can be used for encryption and decryption, thus allowing participants to negotiate carpool details.
(2)
After the originator receives the “GoMatch” message (in Step5), he/she can conduct a Diffie-Hellman key exchange of the key SK
A
B with the participant, and this key can then be used to encrypt the following message.


## 4.4. Comparison

Table1 presents a comparison of our proposed system with scheduling algorithms (e.g., Fagin and Williams [14]) and carpooling matching algorithms (including Lift4U [19] and Lalos et al.’s algorithm [20]). All the algorithms can provide carpool functions, while [19, 20] require GPS for the comparison. In terms of scheduling algorithms, because the system requires prior communication to coordinate matching, the users must know each other prior to using the system. In addition, because scheduling algorithms are planned ahead of time and Lift4U relies on a networked platform for matching, therefore it is unable to provide real-time, spur-of-the-moment carpooling. Most methods require prior registration or login and use networked platforms to run their matching algorithms, thus requiring Internet access. Also, most methods fail to consider privacy concerns. However, the proposed method provides all of these functions, while providing privacy protection.Table 1
Comparison.
Function
Fagin and Williams [14]
Lift4U [19]
Lalos et al. [20]
Proposed system
Carpool
v
v
v
v
Does not require GPS for matching
v
v
Users do not need to know each other
v
v
v
Spur-of-the-moment matching
v
v
Does not require registration
v
Does not require Internet access
v
v
Privacy protection
v


## 5. Implementation

To validate the proposed method, we used the Android development platform to implement the matching program on a NEXUS S smartphone and used the SHA-1 hash algorithm as the hash function for the matching process. Using Wi-Fi as the transmission medium, we conducted actual tests of the privacy-enabled carpool matching system on a smartphone running Android.As the flow chart shows in Figure3, after the user initiates the program (see Figure 6(a)), the program first engages the “Listen” (i.e., “search”) mode (see Figure 6(b)). If it fails to find a ride, it organizes a new carpool (see Figure 6(c)). We assume that Alice initiates a new carpool. She then inputs her approximate intended destination (e.g., city) and uses Wi-Fi to broadcast a carpool or taxi pool message to find potential carpoolers. When multiple users (i.e., participants) receive the carpool or taxi pool message through the “Listen” mode, (see Figure 6(d)), willing parties which match the originator’s query specifications (in this case “Bob”) transmit back a “GoMatch” (i.e., “Join”) message. Alice receives the “GoMatch” message and then decides whether to approve the match (see Figure 6(e)).Implementation.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
(m)
(n)
(o)
(p)Next Alice can opt to use a Diffie-Hellman key exchange (i.e., the “DH receiver”) (see Figure6(f)). If so, both parties will use the Diffie-Hellman key exchange to establish a session key (see Figures 6(g) and 6(h)). Next, Alice inputs her own destination Ds
t
A and error range Rn
g
A (see Figure 6(i)), using map to transmit the converted coordinates, longitude, and latitude (see Figure 6(j)) and generate the resulting adjustments Adj
A with Rng
A for transmission to Bob.Once Bob receivesAdj
A and Rn
g
A, he inputs his own destination Dst
B (see Figure 6(k)), using map to transmit the converted coordinates (see Figure 6(l)). The calculated h
B is then transmitted to Alice who then compares whether H
(
L
L
A
(
q
)
) and h
B are identical (see Figure 6(m)). If the match is successful, Alice sends the “OK” message to Bob. When Bob receives the successful match message (see Figure 6(n)), he and Alice begin to proceed to the carpool negotiation (see Figures 6(o) and 6(p)).


## 6. Conclusion

In this paper, we propose a protocol by which mobile devices can be used to provide instant matching for carpools and taxi pools in a way that protects the information privacy of all parties (e.g., names, telephone numbers, travel times, origins, and destinations). We review previous similar schemes and compare their various features and properties, for example, whether they require the use of GPS, whether the users need to know each other in advance, whether they are required to register, whether they can protect the user’s personal information, and whether they can be used to arrange spontaneous carpools instantly. We also perform a security analysis to illustrate the privacy controls of the proposed scheme. We discuss how to obtain the quantification space and quantized values from the longitudes and latitudes, explain methods for arranging matches within a given error range, and make recommendations for actual system implementation. We also show that matching will succeed as long as the distance between the two parties falls within a set error distance range and will fail if this distance is exceeded. Finally, we describe the implementation of the proposed scheme on an Android smartphone to demonstrate feasibility. Future work will focus on developing a more accurate method for producing “circular pairing” rather than “square pairing” to reduce error values or error ratios arising from the determination of coordinates.



---

*Source: 579031-2014-03-23.xml*