# An Authenticated Privacy-Preserving Mobile Matchmaking Protocol Based on Social Connections with Friendship Ownership

Authors: Shin-Yan Chiou; Chi-Shiu Luo
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The increase of mobile device use for social interaction drives the proliferation of online social applications. However, it prompts a series of security and existence problems. Some common problems are the authenticity of social contacts, the privacy of online communication, and the lack of physical interaction. This work presents mobile private matchmaking protocols that allow users to privately and immediately search the targets which match their planning purposes via mobile devices and wireless network. Based on social networks, the relationships of targets can be unlimited or limited to friends or friends of friends. It considers the privacy of users and the authenticity of friendships. The privacy means that no private information, except chosen targets, is leaked and the authenticity that signifies no forgery relationships can be successfully claimed. It applies to many applications such as searching for a
person to talk to, to dine with, to play games with, or to see a movie with. The proposed scheme is demonstrated to be secure, effective, and efficient. The implementation of the proposed algorithms on Android system mobile devices allows users to securely find their target via mobile phones.


---

## Body

## 1. Introduction

Recently, online social networks (OSN) have received a great deal of attention. They provide online communities of users for information sharing. They also change the way people communicate and interact. Facebook, LinkedIn, Myspace, Flicker, Plurk, and Twitter, for instance, are successful applications of social networking services.However, personal information in OSN is shared among group contacts. Due to the private nature of the shared information, data privacy is an indispensable security requirement in OSN applications. For solving the privacy-related problem, scholars use some valuable methods such as oblivious transfer (OT) [1], identity-based encryption (IBE) [2], searchable encryption [3], privacy-preserving profiles searching (PPPS) [4], access-right revocable scheme [5], middleware for mobile social networking [6], privacy-preserving matchmaking protocol [7], and decentralization-based scheme [8].Beside privacy consideration, authentication [9] is also an important issue for matchmaking schemes, and authentication protocols, such as password-based authentication schemes [10, 11], are required. However, prior to password authentication, key establishment and key agreement [12–16] are needed as well. The first unauthenticated key agreement protocol based on asymmetric cryptographic techniques was proposed by Diffie and Hellman [17, 18]. Later, some authenticated key agreement [19–24] and anonymous key agreement [25, 26] protocols were developed and proposed.MobiClique [6], a mobile social networking middleware, let users’ smartphones broadcast beacons to nearby devices to show their owners' information. MobiClique users download their profile information from Facebook to their devices and send this information to any Bluetooth device nearby for performing a matching. This approach reveals personal private information to anyone.Meet Gatsby [27] and Loopt [28] are interesting websites which can find nearby people with shared interests. They require a trusted server that participates in each matchmaking operation. The server knows the interests and current location of each user and performs matchmaking based on this information. This approach allows the server to track users.However, almost all of the applications are centralized and a trusted server is necessary. This centralized deployment results in some limitations. The users have to connect to the server to use the being controlled data. This brings inconvenience because accessing Internet is not always allowable for all users. All private information of a user is stored in the server, so there is the risk of private information leakage. In addition, each user is only authenticated to the sever, so a user has no capability to verify the information provided by another user. As a result, the issues of centralized deployment lead to inconvenience for mobile usage, leakage of private information, and lack of information authenticity between users.A decentralization-based scheme [8], for privacy issue, suggests a peer-to-peer architecture solution to avoid centralized control for the existing online centralized architecture. It is based on hop-by-hop trust relationships.FindU [29] is a privacy-preserving personal profile matching schemes for mobile social networks. An initiating user can find the one, from a group of users, whose profile best matches with his/her. Only necessary and minimal information about the private attributes of the participating users is exchanged to limit the risk of privacy exposure.Xie and Hengartner [7] proposed another privacy-preserving matchmaking scheme for mobile social networking. They extended AgES [30], which uses commutative encryption, to provide the private matching function. The users' interest items are hashed and then compared for achieving privacy preservation. Therefore, a potentially malicious user learns only the interests that he has in common with a nearby user. Although their protocol does not require a trusted server in matchmaking phase, they need a personal interest signer (in interest signing phase) to sign personal interests in advance. Wang et al. [31] proposed another privacy-preserving matchmaking scheme for mobile social networking to enhance the computational performance of [7]. However in their schemes [7, 31], trusted third parties, identity signer and personal interest signer, are required to issue identity certificates and create interests signatures, and social networking friendships cannot be proved directly.Chiou and Huang [32] and Chiou et al. [33] propose a social-network-based common-friend discovery application which is noncentralized and provides privacy preservation and information authentication. The application aims to find common friends of two users via their personal devices, such as cell phones or PDA, directly, wirelessly and privately.In this paper, we propose a mobile private matchmaking scheme based on social connection. The special advantage and the novelty is that the proposed scheme is non-centralized and provides privacy preservation, mutual authentication, friendship relation verification, and friendship ownership certification, which guarantee that the matchmaking target is a friend of friend. Via mobile devices, users can use Wi-Fi Direct [34] and free personal area network (PAN) such as Bluetooth [35, 36] or Infrared Data Association (IrDA) [37] to communicate with each other without Internet access requirement. The application keeps personal information private. After executing the application, the only information that users share is their common friend. Furthermore, it authenticates the exchanged information and avoids forging problems. In addition, we implement a simulation prototype based on our proposed scheme on mobile phones running under the Android operating system.The rest of this paper is organized as follows. In Section2, we explain terms related to private matching, data ownership certificate, and replay attack resistance. In Section 3, we review related studies. A technical description and construction details for the proposed protocol are, respectively, presented in Sections 4 and 5. Security, efficiency, and performance analysis for the proposed protocol and property comparison between our scheme and related protocols are given in Section 6. Our implementation is described in Section 7, and we provide conclusions and directions for future work in Section 8.


## 2. Preliminaries

This section reviews terminology related to private matching, includingPrivate Matching, Data Ownership Certificates, Asymmetric Exchange, and Replay Attack Resistance.


### 2.1. Private Matching

Freedman et al. [38] defined a private matching (PM) scheme as a two-party protocol between a client (chooser) C and a server (sender) S. The inputs of C and S are sets drawn from the same domain. At the conclusion of the protocol, C determines which special inputs are shared by both C and S. Li et al. [39] also define the security requirement of PM as follows.Definition 1 (security requirements of PM).
Assuming there are two databases,A and B, one is query Q⊂A and one is matching protocol which computes P=Q∩B. The scheme is secure and preserves privacy if it satisfies the following requirements.(1)
Privacy. Each party can only know P and its input to the matching protocol. Aside from this information, no other information is available to either party.(2)
Nonspoof. The items in databases A and B are authorized by their respective owners. This means that the user can only query Q if the owner of the specific query item authorizes the item to the user. In other words, the user cannot generate the query item without authorization from the item owner. In addition, the user is required to present proof of this authorization.


### 2.2. Data Ownership Certificate (DOC)

Li et al. [39] define a Data Ownership Certificate (DOC) as an authorization token, which enables a user to prove his or her legitimate ownership of particular data. The DOC can attest to the data's ownership, provide verifiable element authorization, and prevent spoofing. If the user does not possess the DOC corresponding to the data in question, he or she cannot make queries for the data and convince another person that he or she is a legitimate owner of this data. The DOC can be used with a variety of matching protocols. Two requirements for the security properties of the DOC [39] are defined as follows.Definition 2 ((DOC) security requirements).
Assume Alice and Bob run a matching protocol to obtain informationd. The scheme provides security properties from DOC if it satisfies the following requirements.(1)
Confidentiality. If Bob is not an authorized owner of d, Bob should not be able to learn that Alice possesses d by running a matching protocol directly with Alice.(2)
Authenticity. If Bob is not an authorized owner of d but Alice is an authorized owner of d, Bob should not be able to pollute Alice’s matching result; that is, Bob cannot introduce d into the matching result.Note thatconfidentiality is difficult to achieve cryptographically since we have to consider both privacy and authenticity. Designs that reveal partial information are not acceptable, and schemes that require precomputation by a third party are not desirable. Therefore, sometimes the goal of DOC is referred to as the reduced confidentiality requirement.


### 2.3. Asymmetric Exchange

Assume that Alice and Bob play a private matching game to exchange their listsA and B and, after the game, learn the answer A∩B. Asymmetric exchange (of a private matching game) means that, for both parties to learn the answer A∩B, we must trust one party (e.g., Alice) to send a correct matching result to the other party (e.g., Bob), where Alice is assumed to be the party to make a final pass to send an important result to Bob. In symmetric exchange both parties simultaneously identify their common items through the matching protocol. When the two parties play an asymmetric private matching game, they are assumed to honestly report their friend lists and the corresponding computational results. (The HP [39], AgES [30], and FNS [38] schemes are categorized as asymmetric information exchanges.)


### 2.4. Replay Attack Resistance

A replay attack is a form of network attack in which a valid data transmission is maliciously or fraudulently repeated or delayed [40]. In private matching protocols, replay attack resistance means that an adversary (or the originator) who intercepts or eavesdrops data and retransmits it is unable to effectively obtain private information or to successfully pose as a party running a private matching protocol.


## 2.1. Private Matching

Freedman et al. [38] defined a private matching (PM) scheme as a two-party protocol between a client (chooser) C and a server (sender) S. The inputs of C and S are sets drawn from the same domain. At the conclusion of the protocol, C determines which special inputs are shared by both C and S. Li et al. [39] also define the security requirement of PM as follows.Definition 1 (security requirements of PM).
Assuming there are two databases,A and B, one is query Q⊂A and one is matching protocol which computes P=Q∩B. The scheme is secure and preserves privacy if it satisfies the following requirements.(1)
Privacy. Each party can only know P and its input to the matching protocol. Aside from this information, no other information is available to either party.(2)
Nonspoof. The items in databases A and B are authorized by their respective owners. This means that the user can only query Q if the owner of the specific query item authorizes the item to the user. In other words, the user cannot generate the query item without authorization from the item owner. In addition, the user is required to present proof of this authorization.


## 2.2. Data Ownership Certificate (DOC)

Li et al. [39] define a Data Ownership Certificate (DOC) as an authorization token, which enables a user to prove his or her legitimate ownership of particular data. The DOC can attest to the data's ownership, provide verifiable element authorization, and prevent spoofing. If the user does not possess the DOC corresponding to the data in question, he or she cannot make queries for the data and convince another person that he or she is a legitimate owner of this data. The DOC can be used with a variety of matching protocols. Two requirements for the security properties of the DOC [39] are defined as follows.Definition 2 ((DOC) security requirements).
Assume Alice and Bob run a matching protocol to obtain informationd. The scheme provides security properties from DOC if it satisfies the following requirements.(1)
Confidentiality. If Bob is not an authorized owner of d, Bob should not be able to learn that Alice possesses d by running a matching protocol directly with Alice.(2)
Authenticity. If Bob is not an authorized owner of d but Alice is an authorized owner of d, Bob should not be able to pollute Alice’s matching result; that is, Bob cannot introduce d into the matching result.Note thatconfidentiality is difficult to achieve cryptographically since we have to consider both privacy and authenticity. Designs that reveal partial information are not acceptable, and schemes that require precomputation by a third party are not desirable. Therefore, sometimes the goal of DOC is referred to as the reduced confidentiality requirement.


## 2.3. Asymmetric Exchange

Assume that Alice and Bob play a private matching game to exchange their listsA and B and, after the game, learn the answer A∩B. Asymmetric exchange (of a private matching game) means that, for both parties to learn the answer A∩B, we must trust one party (e.g., Alice) to send a correct matching result to the other party (e.g., Bob), where Alice is assumed to be the party to make a final pass to send an important result to Bob. In symmetric exchange both parties simultaneously identify their common items through the matching protocol. When the two parties play an asymmetric private matching game, they are assumed to honestly report their friend lists and the corresponding computational results. (The HP [39], AgES [30], and FNS [38] schemes are categorized as asymmetric information exchanges.)


## 2.4. Replay Attack Resistance

A replay attack is a form of network attack in which a valid data transmission is maliciously or fraudulently repeated or delayed [40]. In private matching protocols, replay attack resistance means that an adversary (or the originator) who intercepts or eavesdrops data and retransmits it is unable to effectively obtain private information or to successfully pose as a party running a private matching protocol.


## 3. Related Work

We present representative private matching protocols and friend discovery schemes in this section. The private matching protocols include Hash Protocol (HP) [39], AgES's commutative encryption protocol [30], FNP's polynomial-based protocol [38], and Data Ownership Certificate (DOC) [39], which can be combined with the private matching protocols to prevent spoofing; friend discovery schemes [32] include friend discovery scheme (FDS) and replay attack resistant friend discovery scheme (RR-FDS).


### 3.1. Private Matching Protocols

In Hash Protocol (HP) [39], a person who wants to query the common items in the other's database computes hash values of items in his own database and so does the person who is queried. Then they exchange these hash values. By this way, they can find the common items without revealing the information of the unmatched items. On the other hand, Agrawal et al. [30] proposed AgES which uses commutative encryption, instantiating as Enck2(Enck1(x))=Enck1(Enck2(x)), to privately match items.Also, Freedman et al. [38] proposed a polynomial-based private matching scheme. They use the property of homomorphic encryption provided by Paillier cryptosystem [41] to achieve stronger privacy. A variant of their scheme, set cardinality private matching, let A know only the set cardinality of Q∩B, |Q∩B|, but the actual items in this set. It’s more applicable than previous schemes. After that, Kissner and Song [42] extend FNP scheme to support more functionality. However, these polynomial-based schemes usually have efficiency problem.Moreover, HP, AgES, and Freedman et al.’s schemes are categorized to asymmetric exchange of information [39], different from symmetric exchange which both parties know the same information in the matching protocol.Besides those, Li et al. [39] proposed Data Ownership Certificate (DOC) to ensure nonspoof. DOC provides the authorization of items. If a user does not obtain the item and the corresponding DOC, he cannot make the query and convince other users.


### 3.2. Friend Discovery Schemes

To find the common friends of two users, Chiou and Huang [32] proposed friend discovery protocols, friend discovery scheme (FDS), and replay attack resistant friend discovery scheme (RR-FDS) based on extending the HP and DOC [39] primitive to ensure privacy preservation and prevent mutual friendship spoofing, where RR-FDS adds the property of resistance to replay attacks. Two algorithms, CredentialExchange and FriendshipMatching, are defined in their protocol.CredentialExchange(U, V). Users U and V exchange credentials with each other. The credentials include friendship certificates to be used in FriendshipMatching.FriendshipMatching(U, V). Users U and V discover their common friends in a process which preserves privacy, achieves mutual authentication, certifies mutual friendship, and prevents mutual friendship spoofing.Since our scheme is designed based on extending the RR-FDS, we now introduce FriendshipMatching of RR-FDS construction.FriendshipMatching(Alice, Bob). As shown in Figure 1, in this algorithm Alice and Bob privately match their common friends through the following steps.(1)
Bob→Alice,rB, where rB is a random number chosen by Bob.(2)
Alice→Bob, DM(Alice,rB), rA, where DM(Alice,rB)={dm(x,rB)∣x∈F(Alice)}, dm(x,rB)=h(idx∥snx∥rB), and rA is a random number chosen by Alice.(3)
Bob compares DM(Alice,rB) with DM(Bob,rB) to find the matching items DM(Alice∩Bob,rB), where DM(Bob,rB)={dm(x,rB)∣x∈F(Bob)} and DM(Alice∩Bob,rB)=DM(Alice,rB)∩DM(Bob,rB).(4)
Bob→Alice, DM(Alice∩Bob), SIGBob(Alice∩Bob), pkBob,sigskBob(rA),  rB, where SIGBob(Alice∩Bob)={sigskx(h(idx)∥pkBob)∣x∈F(Alice∩Bob)}, and sigskBob(rA) is the signature of rA signed using Bob’s private key skBob.(5)
Alice compares DM(Alice∩Bob,rA) with DM(Alice,rA) to get the matching items DM(Alice∩Bob).(6)
Alice→Bob, SIGAlice(Alice∩Bob), pkAlice, sigskAlice(rB).(7)
Bob verifies sigskAlice(rB) and verifies the signatures of the hash value for the identity of each common friend, concatenating Alice’s public key pkAlice in SIGAlice(Alice∩Bob).Figure 1
FriendshipMatching(Alice, Bob) of RR-FDS.Finally,Alice and Bob recognize their common friends F(Alice∩Bob).


## 3.1. Private Matching Protocols

In Hash Protocol (HP) [39], a person who wants to query the common items in the other's database computes hash values of items in his own database and so does the person who is queried. Then they exchange these hash values. By this way, they can find the common items without revealing the information of the unmatched items. On the other hand, Agrawal et al. [30] proposed AgES which uses commutative encryption, instantiating as Enck2(Enck1(x))=Enck1(Enck2(x)), to privately match items.Also, Freedman et al. [38] proposed a polynomial-based private matching scheme. They use the property of homomorphic encryption provided by Paillier cryptosystem [41] to achieve stronger privacy. A variant of their scheme, set cardinality private matching, let A know only the set cardinality of Q∩B, |Q∩B|, but the actual items in this set. It’s more applicable than previous schemes. After that, Kissner and Song [42] extend FNP scheme to support more functionality. However, these polynomial-based schemes usually have efficiency problem.Moreover, HP, AgES, and Freedman et al.’s schemes are categorized to asymmetric exchange of information [39], different from symmetric exchange which both parties know the same information in the matching protocol.Besides those, Li et al. [39] proposed Data Ownership Certificate (DOC) to ensure nonspoof. DOC provides the authorization of items. If a user does not obtain the item and the corresponding DOC, he cannot make the query and convince other users.


## 3.2. Friend Discovery Schemes

To find the common friends of two users, Chiou and Huang [32] proposed friend discovery protocols, friend discovery scheme (FDS), and replay attack resistant friend discovery scheme (RR-FDS) based on extending the HP and DOC [39] primitive to ensure privacy preservation and prevent mutual friendship spoofing, where RR-FDS adds the property of resistance to replay attacks. Two algorithms, CredentialExchange and FriendshipMatching, are defined in their protocol.CredentialExchange(U, V). Users U and V exchange credentials with each other. The credentials include friendship certificates to be used in FriendshipMatching.FriendshipMatching(U, V). Users U and V discover their common friends in a process which preserves privacy, achieves mutual authentication, certifies mutual friendship, and prevents mutual friendship spoofing.Since our scheme is designed based on extending the RR-FDS, we now introduce FriendshipMatching of RR-FDS construction.FriendshipMatching(Alice, Bob). As shown in Figure 1, in this algorithm Alice and Bob privately match their common friends through the following steps.(1)
Bob→Alice,rB, where rB is a random number chosen by Bob.(2)
Alice→Bob, DM(Alice,rB), rA, where DM(Alice,rB)={dm(x,rB)∣x∈F(Alice)}, dm(x,rB)=h(idx∥snx∥rB), and rA is a random number chosen by Alice.(3)
Bob compares DM(Alice,rB) with DM(Bob,rB) to find the matching items DM(Alice∩Bob,rB), where DM(Bob,rB)={dm(x,rB)∣x∈F(Bob)} and DM(Alice∩Bob,rB)=DM(Alice,rB)∩DM(Bob,rB).(4)
Bob→Alice, DM(Alice∩Bob), SIGBob(Alice∩Bob), pkBob,sigskBob(rA),  rB, where SIGBob(Alice∩Bob)={sigskx(h(idx)∥pkBob)∣x∈F(Alice∩Bob)}, and sigskBob(rA) is the signature of rA signed using Bob’s private key skBob.(5)
Alice compares DM(Alice∩Bob,rA) with DM(Alice,rA) to get the matching items DM(Alice∩Bob).(6)
Alice→Bob, SIGAlice(Alice∩Bob), pkAlice, sigskAlice(rB).(7)
Bob verifies sigskAlice(rB) and verifies the signatures of the hash value for the identity of each common friend, concatenating Alice’s public key pkAlice in SIGAlice(Alice∩Bob).Figure 1
FriendshipMatching(Alice, Bob) of RR-FDS.Finally,Alice and Bob recognize their common friends F(Alice∩Bob).


## 4. Notations and Technical Preliminaries

### 4.1. Notations

Table1 defines the notations used in our proposed protocol. In Table 1, “∥” denotes concatenation and snA is a fixed sufficient long secret string chosen by user A, where “sufficient long” means the string is long enough to resist brute force or cryptographic attacks. In addition, in this scheme, knowing the secret snA implies friendship with user A. Of course, it is not persuasive enough and advanced friendship has to be proven. Moreover, we define MH(T,P) as True if ∀Ti∈T∃pj∈P∋pj∈Ti and as False if not, where P={pj}, T={setsTi}. The symbol T={setsTi} means target profiles, such as T1 = “Job: undergraduate,” T2 = “Gender: female,” T3 = “Age: 18–28.” The symbol P = {pj} means a personal profiles, such as p1 = “Job: freshman,” p2 = “Gender: female,” p3 = “Marriage: unmarried,” p4 = “Age: 19,” and p5 = “Interest: watch movie.” In this case, MH(T,P) = true.Table 1
Notations.
Notation
Meaning
p
k
A
Public key of userA
s
k
A
Private key of userA
i
d
A
Identity of userA
s
n
A
A fixed sufficient long string chosen by userA
h
(
·
)
Cryptographic hash functions
si
g
k
(
m
)
Signature ofm signed using private key k
ve
r
k
(
m
,
s
)
True, ifs is a valid signature of message m verified using public key k; else false
si
g
B
A
si
g
s
k
B
(
h
(
i
d
B
)
|
|
p
k
A
)
d
m
(
A
)
h
(
i
d
A
|
|
s
n
A
)
d
m
(
A
,
r
)
h
(
i
d
A
|
|
s
n
A
|
|
r
)
F
(
A
)
{
x
|
x is the friend of user A}
F
(
A
∩
B
)
F
(
A
)
∩
F
(
B
)
=
{
x
|
x
∈
F
(
A
) and x∈F(B)}
F
(
A
∪
B
)
F
(
A
)
∪
F
(
B
)
=
{
x
|
x
∈
F
(
A
) or x∈F(B)}
F
(
A
-
B
)
F
(
A
)
-
F
(
B
)
=
{
x
|
x
∈
F
(
A
) and x∉F(B)}
D
M
(
A
)
{
d
m
(
x
)
|
x
∈
F
(
A
)
}
D
M
(
A
,
r
)
{
d
m
(
x
,
r
)
|
x
∈
F
(
A
)
}
D
M
(
A
∩
B
)
D
M
(
A
)
∩
D
M
(
B
)
D
M
(
A
∩
B
,
r
)
D
M
(
A
,
r
)
∩
D
M
(
B
,
r
)
E
n
p
k
A
(
M
)
EncryptM using public key pkA
D
e
s
k
A
(
C
)
DecryptC using private key skA
E
K
(
M
)
EncryptM using symmetric key K
D
K
(
C
)
DecryptC using symmetric key K
SI
G
A
(
B
)
{
si
g
x
A
|
x
∈
F
(
B
)
}
SI
G
A
(
B
∩
C
)
{
si
g
x
A
|
x
∈
F
(
B
) and x∈F(C)}
FC
L
A
Friendship certificate list of userA
M
H
(
T
,
P
)
True, if∀Ti∈T∃pj∈P∋pj∈Ti; false, else
WhereP= sets {pj},T= sets {Ti}.


### 4.2. Security Requirements

The security requirements of our proposed protocol are as follows.(1)
Privacy Preservation. Users can only learn the identity of common friends and nothing else.(2)
Mutual Authentication. Users can authenticate one another.(3)
Mutual Friendship Certification. Users can prove their friendship to each other. (It is also named data authenticity.)(4)
Mutual Prevention of Friendship Spoofing. Malicious users are prevented from manipulating these friendship certificates.(5)
ReplayAttack Resistance. An adversary (or the originator), who intercepts or eavesdrops the data and retransmits it is prevented from successfully obtaining private information or posing as a party running a private matchmaking protocol.


## 4.1. Notations

Table1 defines the notations used in our proposed protocol. In Table 1, “∥” denotes concatenation and snA is a fixed sufficient long secret string chosen by user A, where “sufficient long” means the string is long enough to resist brute force or cryptographic attacks. In addition, in this scheme, knowing the secret snA implies friendship with user A. Of course, it is not persuasive enough and advanced friendship has to be proven. Moreover, we define MH(T,P) as True if ∀Ti∈T∃pj∈P∋pj∈Ti and as False if not, where P={pj}, T={setsTi}. The symbol T={setsTi} means target profiles, such as T1 = “Job: undergraduate,” T2 = “Gender: female,” T3 = “Age: 18–28.” The symbol P = {pj} means a personal profiles, such as p1 = “Job: freshman,” p2 = “Gender: female,” p3 = “Marriage: unmarried,” p4 = “Age: 19,” and p5 = “Interest: watch movie.” In this case, MH(T,P) = true.Table 1
Notations.
Notation
Meaning
p
k
A
Public key of userA
s
k
A
Private key of userA
i
d
A
Identity of userA
s
n
A
A fixed sufficient long string chosen by userA
h
(
·
)
Cryptographic hash functions
si
g
k
(
m
)
Signature ofm signed using private key k
ve
r
k
(
m
,
s
)
True, ifs is a valid signature of message m verified using public key k; else false
si
g
B
A
si
g
s
k
B
(
h
(
i
d
B
)
|
|
p
k
A
)
d
m
(
A
)
h
(
i
d
A
|
|
s
n
A
)
d
m
(
A
,
r
)
h
(
i
d
A
|
|
s
n
A
|
|
r
)
F
(
A
)
{
x
|
x is the friend of user A}
F
(
A
∩
B
)
F
(
A
)
∩
F
(
B
)
=
{
x
|
x
∈
F
(
A
) and x∈F(B)}
F
(
A
∪
B
)
F
(
A
)
∪
F
(
B
)
=
{
x
|
x
∈
F
(
A
) or x∈F(B)}
F
(
A
-
B
)
F
(
A
)
-
F
(
B
)
=
{
x
|
x
∈
F
(
A
) and x∉F(B)}
D
M
(
A
)
{
d
m
(
x
)
|
x
∈
F
(
A
)
}
D
M
(
A
,
r
)
{
d
m
(
x
,
r
)
|
x
∈
F
(
A
)
}
D
M
(
A
∩
B
)
D
M
(
A
)
∩
D
M
(
B
)
D
M
(
A
∩
B
,
r
)
D
M
(
A
,
r
)
∩
D
M
(
B
,
r
)
E
n
p
k
A
(
M
)
EncryptM using public key pkA
D
e
s
k
A
(
C
)
DecryptC using private key skA
E
K
(
M
)
EncryptM using symmetric key K
D
K
(
C
)
DecryptC using symmetric key K
SI
G
A
(
B
)
{
si
g
x
A
|
x
∈
F
(
B
)
}
SI
G
A
(
B
∩
C
)
{
si
g
x
A
|
x
∈
F
(
B
) and x∈F(C)}
FC
L
A
Friendship certificate list of userA
M
H
(
T
,
P
)
True, if∀Ti∈T∃pj∈P∋pj∈Ti; false, else
WhereP= sets {pj},T= sets {Ti}.


## 4.2. Security Requirements

The security requirements of our proposed protocol are as follows.(1)
Privacy Preservation. Users can only learn the identity of common friends and nothing else.(2)
Mutual Authentication. Users can authenticate one another.(3)
Mutual Friendship Certification. Users can prove their friendship to each other. (It is also named data authenticity.)(4)
Mutual Prevention of Friendship Spoofing. Malicious users are prevented from manipulating these friendship certificates.(5)
ReplayAttack Resistance. An adversary (or the originator), who intercepts or eavesdrops the data and retransmits it is prevented from successfully obtaining private information or posing as a party running a private matchmaking protocol.


## 5. Proposed Scheme

The proposed protocols, mobile private matchmaking (MPM), developed in this paper are based on extending the RR-FDS of Chiou and Huang protocol [32], primitive to ensure privacy preservation, prevent mutual friendship spoofing, and provide friendship discovery. The protocols are defined as three algorithms, Init, CredentialIssue, and AuthObjectMatching. We first describe the syntax of MPM with privacy and authenticity and then present the specification of our protocol.


### 5.1. Syntax of MPM with Privacy and Authenticity

MPM consists of three algorithms as follows.Init
(
1
κ
)
Algorithm. This algorithm is executed once by each user Ui. On input of a security parameter 1κ, it initializes internal parameters, generates public key pkUi and private key skUi, and clears Ui’s friendship certificate list, that is, FCLUi=ϕ (an empty set).Credentiallssue(U,V). This is credential issue protocol executed by users U and V. U issues a personal credential CrdUV to V, and V issues CrdVU to U. CrdVU and CrdUV are added to friendship certificate lists FCLU and FCLV, respectively. The credentials stand for the friendship between U and V. They are used in matching to show friendship and provide the friendship evidence. The inputs of U and V are (idU, pkU, skU, snU) and (idV, pkV, skV, snV), where idU is the identity of user U, pkU is the public key of user U, skU is the private key of user U, and snU is a fixed sufficient long string chosen by user U.AuthObjectMatching(U,V). This is an authenticated object matching protocol executed by users U and V. In this protocol, U and V hope to find a matched object and their common friendship is also checked. It is designed as two-state mechanism such that U is an initializer and V is a responder. The inputs of U and V are (TU, PU, snU, pkU, skU, FCLU) and (TV, PV, snV, pkV, skV, FCLV), where TU is U’s target profile which consists of the profiles of the target object and PU is U’s personal profile which consists of the profiles of user U.MPM allows users to find a matched object, recognize their common friends, and authenticate to each other. It proves friendship-credential ownership and replay attack resistance. The correctness and security of MPM are defined in Definitions3 and 4.Definition 3 (correctness of MPM).
Assume that usersU and V interact in a MPM protocol with input (TU, PU, snU, pkU, skU, FCLU) and (TV, PV, snV, pkV, skV, FCLV), respectively, and let πU and πV denote the corresponding sessions. By ID∩ we denote the set of identities that appears in both FCLU and FCLV. MPM scheme is correct if (1) (find out a matched object)  πU and πV complete in the same state, which is accepted if and only if MH(TU,PV)=MH(TV,PU)=true or is rejected if U or V gets “not right object” information; (2) (friend discovery) both U and V learn F(U∩V); (3) (mutual authentication)  U and V can authenticate each other; (4) (friendship proof)  U and V can prove their friendship of F(U∩V).Definition 4 (security of MPM).
Assume that usersU and V interact in a MPM protocol with inputs (TU, PU, snU, pkU, skU, FCLU) and (TV, PV, snV, pkV, skV, FCLV), respectively. MPM scheme is secure if (1) (privacy preservation)  U and V only learn F(V∩U) and nothing else (i.e., U learns nothing about F(V-U) and V learns nothing about F(U-V)); (2) (mutual authentication)  U and V can authenticate to each other; (3) (mutual friendship ownership certification)  U and V can prove their friendship to each other via the signatures of pkU and pkV signed using the private keys of their friends; (4) (mutual prevention of friendship spoofing) malicious users are prevented from manipulating these friendship credentials including SIGU(U) and SIGV(V) even if they obtain FCLU or FCLV; and (5) (replay-attack resistance) an adversary, including U and V, who intercepts or eavesdrops the data and retransmits it, fails to obtain private information or to pose as a party U or V running a private matchmaking protocol.


### 5.2. The Protocol Specification

Based on Definitions3 and 4, three algorithms Init, CredentialExchange, and AuthObjectMatching of MPM are presented as follows.Init
(
1
κ
)
Algorithm. The set-up routine run by each user U mainly consists of the generation of safe RSA [43] parameters. Given security parameter κ, two κ-bit safe primes P and Q are picked randomly. The RSA modulus is set to N=PQ, and a pair e,d∈Zφ(N) is chosen such that ed=1 (mod φ(N)). We denote pkU=e is a public key and skU=d is a private key. (The underlying cryptosystem can also be ECC [44] or other cryptographic systems).CredentialExchange ((idU,pkU,skU, snU), (idV,pkV,skV, and snV)) Protocol. Users U and V generate personal credentials CrdUV and CrdVU for each other as follows.(1)
U→V,idU,pkU, where idU is the identity of U and pkU is the public key of U. The underlying public key cryptosystem can use RSA [43], ECC [44], or other cryptosystems. Note that the key pair pk and sk is generated by each user, not by a trusted third party such as CA.(2)
V computes sigVU=sigskV(h(idV)∥pkU) to prove his friendship ownership to U, where h(·) is a cryptographic hash function, such as SHA1 [45] or MD5 [46], skV is the private key of V, and sigskV(·) represents the signature signed using key skV.(3)
V→U,idV,pkV,snV,sigVU, where snV is a sufficiently long string chosen by V.(4)
U verifies sigVU. If verpkV((h(idV)∥pkU),sigVU) is true, he computes sigUV=sigskU(h(idU)∥pkV). Else, send “fail” to V and this algorithm fails.(5)
U→V,snU,sigUV.(6)
V verifies sigUV. If verpkU((h(idU)∥pkV),sigUV) is true, finish this algorithm successfully. Else, fail this algorithm.Finally,U adds CrdVU=(idV,pkV,snV,sigVU) in FCLU and V adds CrdUV=(idU,pkU,snU,sigUV) in FCLV, where FCLU means friendship certificate list of U.An example of CredentialExchange(Alice, Bob) is shown in Figure2. Note that snU and snV should be protected from eavesdropping in CredentialExchange. This algorithm can usually be performed via Bluetooth [35, 36], which provides a basic confidentiality service to thwart eavesdropping attempts on packet payloads exchanged between Bluetooth devices [47]. Otherwise, snU and snV can be encrypted using public keys, pkV and pkU, which can be authenticated via Bluetooth device authentication procedures [47].Figure 2
CredentialExchange(Alice, Bob).AuthObjectMatching ((TU, PU, snU, pkU, skU, FCLU), (TV, PV, snV, pkV, skV, FCLV)) Protocol. Users U and V hope to find a matched object via this protocol. It is designed that U is the initializer and V is the responder. The protocol is shown as follows. (Also see Figures 3 and 4).(1)
U, who chooses to be an initializer, broadcasts pkU,rU, where rU is a random number chosen by U.(2)
V (who chooses to be a responder) →U,  EnpkU(rV), DM(V,rU⊕rV), pkV, sigskV(rU), where DM(V,rU⊕rV)={dm(Vj,rU⊕rV)∣Vj∈F(V)}.(3)
U gets rV=DeskU(EnpkU(rV)) and compares DM(V,rU⊕rV) with DM(U,rU⊕rV) to find the matching items DM(U∩V,rU⊕rV), where DM(U∩V,rU⊕rV)=DM(U,rU⊕rV)∩DM(V,rU⊕rV). If DM(U∩V,rU⊕rV)=∅, U and V have no friends in common. U then sends V a “no match” message and terminates the algorithm. Else, U verifies, if verpkV(rU,sigskV(rU)) is true. If it is true, the algorithm proceeds to the next step. Else, U sends a “failure” message and terminates the algorithm.(4)
U→V, DM(U∩V,rV), SIGU(U∩V), sigskU(rV), EnpkV(KUV), EKUV(TU).(5)
V compares DM(U∩V,rV) with DM(V,rV) to get the matching items DM(U∩V) and then verifies sigskU(rV) and SIGU(U∩V). If either verpkU(rV,sigskU(rV)) or verpkVj((h(idVj)∥pkU),  sigskVj(h(idVj)∥pkV)) is false, V sends “failure”, and terminates this algorithm, where Vj∈DM(U∩V). Else, V computes secret key KUV=DeskV(EnpkV(KUV)) and gets TU=DKUV(EKUV(TU)). If MH(TU,PV) ≠ true, which means V is not the right object, V sends a “not right object” message and terminates this algorithm, where PV is V’s personal profile. Else, the algorithm proceeds to the next step.(6)
V→U, SIGV(U∩V), EKUV(TV).(7)
U verifies SIGV(U∩V). If verpkUj((h(idUi)∥pkV),  sigskUi(h(idUi)∥pkU)) is true, U computes TV=DKUV(EKUV(TV)), where Ui∈DM(U∩V). Else, U sends a “failure” message and terminates the algorithm. If MH(TV,PU) is false, which means U is not the right object, U sends a “not right object” message and terminates the algorithm. Else, the algorithm proceeds to the next step.(8)
U↔V,EKUV(time,location,…). U and V find their target objects V and U and negotiate a time, location, and others confidentially.Figure 3
Broadcast of MPM scheme.Figure 4
Authenticated object matching.U and V can recognize their common friends F(U∩V). In AuthObjectMatching, step 8 can be combined into steps 4 and 6 to reduce transmission times. Notice that no information aside from F(U∩V) is disclosed. That is, U does not learn any information about F(V-U), and U does not learn any information about F(V-U). Moreover, observe that no trusted centralized server is needed in the proposed protocol.


## 5.1. Syntax of MPM with Privacy and Authenticity

MPM consists of three algorithms as follows.Init
(
1
κ
)
Algorithm. This algorithm is executed once by each user Ui. On input of a security parameter 1κ, it initializes internal parameters, generates public key pkUi and private key skUi, and clears Ui’s friendship certificate list, that is, FCLUi=ϕ (an empty set).Credentiallssue(U,V). This is credential issue protocol executed by users U and V. U issues a personal credential CrdUV to V, and V issues CrdVU to U. CrdVU and CrdUV are added to friendship certificate lists FCLU and FCLV, respectively. The credentials stand for the friendship between U and V. They are used in matching to show friendship and provide the friendship evidence. The inputs of U and V are (idU, pkU, skU, snU) and (idV, pkV, skV, snV), where idU is the identity of user U, pkU is the public key of user U, skU is the private key of user U, and snU is a fixed sufficient long string chosen by user U.AuthObjectMatching(U,V). This is an authenticated object matching protocol executed by users U and V. In this protocol, U and V hope to find a matched object and their common friendship is also checked. It is designed as two-state mechanism such that U is an initializer and V is a responder. The inputs of U and V are (TU, PU, snU, pkU, skU, FCLU) and (TV, PV, snV, pkV, skV, FCLV), where TU is U’s target profile which consists of the profiles of the target object and PU is U’s personal profile which consists of the profiles of user U.MPM allows users to find a matched object, recognize their common friends, and authenticate to each other. It proves friendship-credential ownership and replay attack resistance. The correctness and security of MPM are defined in Definitions3 and 4.Definition 3 (correctness of MPM).
Assume that usersU and V interact in a MPM protocol with input (TU, PU, snU, pkU, skU, FCLU) and (TV, PV, snV, pkV, skV, FCLV), respectively, and let πU and πV denote the corresponding sessions. By ID∩ we denote the set of identities that appears in both FCLU and FCLV. MPM scheme is correct if (1) (find out a matched object)  πU and πV complete in the same state, which is accepted if and only if MH(TU,PV)=MH(TV,PU)=true or is rejected if U or V gets “not right object” information; (2) (friend discovery) both U and V learn F(U∩V); (3) (mutual authentication)  U and V can authenticate each other; (4) (friendship proof)  U and V can prove their friendship of F(U∩V).Definition 4 (security of MPM).
Assume that usersU and V interact in a MPM protocol with inputs (TU, PU, snU, pkU, skU, FCLU) and (TV, PV, snV, pkV, skV, FCLV), respectively. MPM scheme is secure if (1) (privacy preservation)  U and V only learn F(V∩U) and nothing else (i.e., U learns nothing about F(V-U) and V learns nothing about F(U-V)); (2) (mutual authentication)  U and V can authenticate to each other; (3) (mutual friendship ownership certification)  U and V can prove their friendship to each other via the signatures of pkU and pkV signed using the private keys of their friends; (4) (mutual prevention of friendship spoofing) malicious users are prevented from manipulating these friendship credentials including SIGU(U) and SIGV(V) even if they obtain FCLU or FCLV; and (5) (replay-attack resistance) an adversary, including U and V, who intercepts or eavesdrops the data and retransmits it, fails to obtain private information or to pose as a party U or V running a private matchmaking protocol.


## 5.2. The Protocol Specification

Based on Definitions3 and 4, three algorithms Init, CredentialExchange, and AuthObjectMatching of MPM are presented as follows.Init
(
1
κ
)
Algorithm. The set-up routine run by each user U mainly consists of the generation of safe RSA [43] parameters. Given security parameter κ, two κ-bit safe primes P and Q are picked randomly. The RSA modulus is set to N=PQ, and a pair e,d∈Zφ(N) is chosen such that ed=1 (mod φ(N)). We denote pkU=e is a public key and skU=d is a private key. (The underlying cryptosystem can also be ECC [44] or other cryptographic systems).CredentialExchange ((idU,pkU,skU, snU), (idV,pkV,skV, and snV)) Protocol. Users U and V generate personal credentials CrdUV and CrdVU for each other as follows.(1)
U→V,idU,pkU, where idU is the identity of U and pkU is the public key of U. The underlying public key cryptosystem can use RSA [43], ECC [44], or other cryptosystems. Note that the key pair pk and sk is generated by each user, not by a trusted third party such as CA.(2)
V computes sigVU=sigskV(h(idV)∥pkU) to prove his friendship ownership to U, where h(·) is a cryptographic hash function, such as SHA1 [45] or MD5 [46], skV is the private key of V, and sigskV(·) represents the signature signed using key skV.(3)
V→U,idV,pkV,snV,sigVU, where snV is a sufficiently long string chosen by V.(4)
U verifies sigVU. If verpkV((h(idV)∥pkU),sigVU) is true, he computes sigUV=sigskU(h(idU)∥pkV). Else, send “fail” to V and this algorithm fails.(5)
U→V,snU,sigUV.(6)
V verifies sigUV. If verpkU((h(idU)∥pkV),sigUV) is true, finish this algorithm successfully. Else, fail this algorithm.Finally,U adds CrdVU=(idV,pkV,snV,sigVU) in FCLU and V adds CrdUV=(idU,pkU,snU,sigUV) in FCLV, where FCLU means friendship certificate list of U.An example of CredentialExchange(Alice, Bob) is shown in Figure2. Note that snU and snV should be protected from eavesdropping in CredentialExchange. This algorithm can usually be performed via Bluetooth [35, 36], which provides a basic confidentiality service to thwart eavesdropping attempts on packet payloads exchanged between Bluetooth devices [47]. Otherwise, snU and snV can be encrypted using public keys, pkV and pkU, which can be authenticated via Bluetooth device authentication procedures [47].Figure 2
CredentialExchange(Alice, Bob).AuthObjectMatching ((TU, PU, snU, pkU, skU, FCLU), (TV, PV, snV, pkV, skV, FCLV)) Protocol. Users U and V hope to find a matched object via this protocol. It is designed that U is the initializer and V is the responder. The protocol is shown as follows. (Also see Figures 3 and 4).(1)
U, who chooses to be an initializer, broadcasts pkU,rU, where rU is a random number chosen by U.(2)
V (who chooses to be a responder) →U,  EnpkU(rV), DM(V,rU⊕rV), pkV, sigskV(rU), where DM(V,rU⊕rV)={dm(Vj,rU⊕rV)∣Vj∈F(V)}.(3)
U gets rV=DeskU(EnpkU(rV)) and compares DM(V,rU⊕rV) with DM(U,rU⊕rV) to find the matching items DM(U∩V,rU⊕rV), where DM(U∩V,rU⊕rV)=DM(U,rU⊕rV)∩DM(V,rU⊕rV). If DM(U∩V,rU⊕rV)=∅, U and V have no friends in common. U then sends V a “no match” message and terminates the algorithm. Else, U verifies, if verpkV(rU,sigskV(rU)) is true. If it is true, the algorithm proceeds to the next step. Else, U sends a “failure” message and terminates the algorithm.(4)
U→V, DM(U∩V,rV), SIGU(U∩V), sigskU(rV), EnpkV(KUV), EKUV(TU).(5)
V compares DM(U∩V,rV) with DM(V,rV) to get the matching items DM(U∩V) and then verifies sigskU(rV) and SIGU(U∩V). If either verpkU(rV,sigskU(rV)) or verpkVj((h(idVj)∥pkU),  sigskVj(h(idVj)∥pkV)) is false, V sends “failure”, and terminates this algorithm, where Vj∈DM(U∩V). Else, V computes secret key KUV=DeskV(EnpkV(KUV)) and gets TU=DKUV(EKUV(TU)). If MH(TU,PV) ≠ true, which means V is not the right object, V sends a “not right object” message and terminates this algorithm, where PV is V’s personal profile. Else, the algorithm proceeds to the next step.(6)
V→U, SIGV(U∩V), EKUV(TV).(7)
U verifies SIGV(U∩V). If verpkUj((h(idUi)∥pkV),  sigskUi(h(idUi)∥pkU)) is true, U computes TV=DKUV(EKUV(TV)), where Ui∈DM(U∩V). Else, U sends a “failure” message and terminates the algorithm. If MH(TV,PU) is false, which means U is not the right object, U sends a “not right object” message and terminates the algorithm. Else, the algorithm proceeds to the next step.(8)
U↔V,EKUV(time,location,…). U and V find their target objects V and U and negotiate a time, location, and others confidentially.Figure 3
Broadcast of MPM scheme.Figure 4
Authenticated object matching.U and V can recognize their common friends F(U∩V). In AuthObjectMatching, step 8 can be combined into steps 4 and 6 to reduce transmission times. Notice that no information aside from F(U∩V) is disclosed. That is, U does not learn any information about F(V-U), and U does not learn any information about F(V-U). Moreover, observe that no trusted centralized server is needed in the proposed protocol.


## 6. Analysis of Proposed Scheme

### 6.1. Security Analysis

We analyze the security of our protocols according to the requirements defined in Definition4.Privacy Preservation. For U, since each dm(Ui,TS) in DM(Alice,TS) is the hash values of idUi, snUi, and TS, V or other persons do not know the meaning of dm(Ui,TS) unless he or she has the same pair of idUi and snUi, where Ui∈F(U). Therefore, the information of their noncommon friends is kept private. (Similar to V, the information of his friends is kept private.)Mutual Authentication.  UA can authenticate UB from the response messages SIGUB(UA∩UB), pkUB and sigskUB(rUA) since rUA is a random number chosen from UA, and pkUB is signed from F(UA∩UB) in SIGUB(UA∩UB).Mutual Friendship Ownership Certification. From SIGUA(UA∩UB), UA can prove her friendships of F(UA∩UB) to UB, because F(UA∩UB) signed the pkUA in SIGUA(UA∩UB) and UB can verify the signature using the public keys of F(UA∩UB).Mutual Prevention of Friendship Spoofing. Since users U and V have to provide the signatures (SIGU(U∩V), sigskV(rU)) and (SIGU(U∩V), sigskU(rV)) to each other to prove they are the person who is the friend of U∩V, no one can spoof the friendship without (U∩V)’s signature and his/her own private key.Replay Attack Resistance.  U transmits DM(U,TS) to V using time TS and V transmits DM(U∩V,rU) to U using the chosen number rU. Since the values TS and rU change, the values DM(U,TS) and DM(U∩V,rU) are different in different matching. Therefore, MPM can resist replay attacks.


### 6.2. Protocol Efficiency and Performance

In this subsection, we analyze the performance of our proposed methods and compare them with other protocols. Table2 summarizes the symbols used in the comparison. MPM costs are then examined, with communication cost and computational cost, respectively, compared in Table 3. For CredentialExchange, the communication cost is 8lS, the computational cost is 2(TS+TV+TH), and the total transaction number is 3.Table 2
Symbols used in performance analysis.
Symbol
Meaning
a
The number of Alice's friends (e.g., 200)
b
The number of Bob's friends (e.g., 200)
r
The number of common friends (e.g., 2)
l
H
Length of the output of hash function (e.g., 128 bits)
l
S
Length of id,sn, pk, and sig (e.g., 1024 bits)
l
TP
Length of Target Profile
T
H
The cost of hashing
T
M
H
The cost of profile matching
T
E
The cost of running symmetric key encryption/decryption algorithm
T
En
The cost of running public key encryption/decryption algorithm
T
S
The cost of running public key signature generation algorithm
T
V
The cost of running public key verification algorithmTable 3
Cost of MPM.
Item
Alice
Bob
Communication cost
(
r
+
2
)
l
S + r·lH + lTP
(
r
+
3
)
l
S + b·lH + lTP
Computational cost
T
S
+
(
r
+
1
)
T
V
+
(
a
+
r
)
T
H
+
2
(
T
E
+
T
En
) + (a+b)log⁡a
T
S
+
(
r
+
1
)
T
V
+
2
b
T
H
+
2
(
T
E
+
T
En
) + (b+r)log⁡b
Transaction number
2
2The communication costs ofAlice and Bob are (r+2)lS+r·lH+lTP and (r+3)lS + b·lH + lTP, and the total transaction number is 4, where lTP means the length of Target Profile. Here we ignore the costs pkU,rU (initial broadcast), and EKUV(time,location,…) (the negotiation between U and V encrypted using the session key KUV).Both the computational costs ofAlice and Bob are approximately TS+(r+1)TV+2TEn since TS, TV, and TEn cost much time comparing TH and TE. Assume each of TS, TV, and TEn is about 1ms and r=2 then the computational time of Alice and Bob are approximately 6 ms, which is efficient in both computation.


### 6.3. Property and Performance Comparison

The properties and performances of the proposed protocol MPM are compared with Xie and Hengartner’s protocol [7] and Wang et al.'s protocol [31] in Tables 4–6. Comparing Tables 3, 4, and 5, we can see the performance of the proposed scheme is much better in all aspects, where rI represents the number of common interests or attributes, lI/lM/lr stands for the length of an interest or attribute/a confirm message/the size of intersection set, and VS represents the trusted third party Verification Server. All these schemes provide privacy preservation, mutual authentication, and replay attack resistance. However, the schemes of Xie and Hengartner [7] and Wang et al. [31] need thrusted third parties, identity signer, and personal interest signer, to issue identity certificates and create interests signatures. In addition, only our scheme provides the functions of friendship relation and friendship ownership certification, which guarantee that the matchmaking target is a friend of friend.Table 4
Cost of Xie and Hengartner protocol [7].
Item
Alice
Bob
Communication cost
(
2
a
+
2
b
+
r
I
+
6
)
l
S + rIlI + lH
(
2
a
+
2
b
+
r
I
+
4
)
l
S + rIlI
Computational cost
3
T
S
+
(
a
+
b
)
T
V
+
T
H
+
(
b
+
r
I
+
2
)
T
E + (a+b)log⁡a
2
T
S
+
(
a
+
b
)
T
V
+
(
a
+
r
I
+
2
)
T
E + (b+a)log⁡b
Transaction number
6
4Table 5
Cost of Wang et al.'s protocol [31].
Item
Alice
Bob
VS
Communication cost
(
a
+
3
b
+
5
)
l
S
+
l
H + lr + rIlI
(
3
a
+
b
+
4
)
l
S
+
l
r + rIlI
2
l
M
Computational cost
3
T
S
+
b
T
V
+
T
H
+
(
b
+
r
I
)
T
E
+
2
(
a
+
b
)
log
⁡
a
+
1
2
T
S
+
a
T
V
+
T
H
+
(
a
+
r
I
)
T
E
+
2
(
b
+
a
)
log
⁡
b
+
1
2
r
log
⁡
r
Transaction number
5
+
1
4
+
1
2Table 6
Comparison of properties.
Xie and Hengartner protocol [7]
Wang  et al. protocol [31]
Proposed protocol
Privacy preservation
√
√
√
Mutual authentication
√
√
√
Replay attack resistance
√
√
√
Non-TTP requirement
√
Nonidentity signer
√
Nonpersonal interest signer
√
Friendship relations
√
Friendship ownership certification
√


## 6.1. Security Analysis

We analyze the security of our protocols according to the requirements defined in Definition4.Privacy Preservation. For U, since each dm(Ui,TS) in DM(Alice,TS) is the hash values of idUi, snUi, and TS, V or other persons do not know the meaning of dm(Ui,TS) unless he or she has the same pair of idUi and snUi, where Ui∈F(U). Therefore, the information of their noncommon friends is kept private. (Similar to V, the information of his friends is kept private.)Mutual Authentication.  UA can authenticate UB from the response messages SIGUB(UA∩UB), pkUB and sigskUB(rUA) since rUA is a random number chosen from UA, and pkUB is signed from F(UA∩UB) in SIGUB(UA∩UB).Mutual Friendship Ownership Certification. From SIGUA(UA∩UB), UA can prove her friendships of F(UA∩UB) to UB, because F(UA∩UB) signed the pkUA in SIGUA(UA∩UB) and UB can verify the signature using the public keys of F(UA∩UB).Mutual Prevention of Friendship Spoofing. Since users U and V have to provide the signatures (SIGU(U∩V), sigskV(rU)) and (SIGU(U∩V), sigskU(rV)) to each other to prove they are the person who is the friend of U∩V, no one can spoof the friendship without (U∩V)’s signature and his/her own private key.Replay Attack Resistance.  U transmits DM(U,TS) to V using time TS and V transmits DM(U∩V,rU) to U using the chosen number rU. Since the values TS and rU change, the values DM(U,TS) and DM(U∩V,rU) are different in different matching. Therefore, MPM can resist replay attacks.


## 6.2. Protocol Efficiency and Performance

In this subsection, we analyze the performance of our proposed methods and compare them with other protocols. Table2 summarizes the symbols used in the comparison. MPM costs are then examined, with communication cost and computational cost, respectively, compared in Table 3. For CredentialExchange, the communication cost is 8lS, the computational cost is 2(TS+TV+TH), and the total transaction number is 3.Table 2
Symbols used in performance analysis.
Symbol
Meaning
a
The number of Alice's friends (e.g., 200)
b
The number of Bob's friends (e.g., 200)
r
The number of common friends (e.g., 2)
l
H
Length of the output of hash function (e.g., 128 bits)
l
S
Length of id,sn, pk, and sig (e.g., 1024 bits)
l
TP
Length of Target Profile
T
H
The cost of hashing
T
M
H
The cost of profile matching
T
E
The cost of running symmetric key encryption/decryption algorithm
T
En
The cost of running public key encryption/decryption algorithm
T
S
The cost of running public key signature generation algorithm
T
V
The cost of running public key verification algorithmTable 3
Cost of MPM.
Item
Alice
Bob
Communication cost
(
r
+
2
)
l
S + r·lH + lTP
(
r
+
3
)
l
S + b·lH + lTP
Computational cost
T
S
+
(
r
+
1
)
T
V
+
(
a
+
r
)
T
H
+
2
(
T
E
+
T
En
) + (a+b)log⁡a
T
S
+
(
r
+
1
)
T
V
+
2
b
T
H
+
2
(
T
E
+
T
En
) + (b+r)log⁡b
Transaction number
2
2The communication costs ofAlice and Bob are (r+2)lS+r·lH+lTP and (r+3)lS + b·lH + lTP, and the total transaction number is 4, where lTP means the length of Target Profile. Here we ignore the costs pkU,rU (initial broadcast), and EKUV(time,location,…) (the negotiation between U and V encrypted using the session key KUV).Both the computational costs ofAlice and Bob are approximately TS+(r+1)TV+2TEn since TS, TV, and TEn cost much time comparing TH and TE. Assume each of TS, TV, and TEn is about 1ms and r=2 then the computational time of Alice and Bob are approximately 6 ms, which is efficient in both computation.


## 6.3. Property and Performance Comparison

The properties and performances of the proposed protocol MPM are compared with Xie and Hengartner’s protocol [7] and Wang et al.'s protocol [31] in Tables 4–6. Comparing Tables 3, 4, and 5, we can see the performance of the proposed scheme is much better in all aspects, where rI represents the number of common interests or attributes, lI/lM/lr stands for the length of an interest or attribute/a confirm message/the size of intersection set, and VS represents the trusted third party Verification Server. All these schemes provide privacy preservation, mutual authentication, and replay attack resistance. However, the schemes of Xie and Hengartner [7] and Wang et al. [31] need thrusted third parties, identity signer, and personal interest signer, to issue identity certificates and create interests signatures. In addition, only our scheme provides the functions of friendship relation and friendship ownership certification, which guarantee that the matchmaking target is a friend of friend.Table 4
Cost of Xie and Hengartner protocol [7].
Item
Alice
Bob
Communication cost
(
2
a
+
2
b
+
r
I
+
6
)
l
S + rIlI + lH
(
2
a
+
2
b
+
r
I
+
4
)
l
S + rIlI
Computational cost
3
T
S
+
(
a
+
b
)
T
V
+
T
H
+
(
b
+
r
I
+
2
)
T
E + (a+b)log⁡a
2
T
S
+
(
a
+
b
)
T
V
+
(
a
+
r
I
+
2
)
T
E + (b+a)log⁡b
Transaction number
6
4Table 5
Cost of Wang et al.'s protocol [31].
Item
Alice
Bob
VS
Communication cost
(
a
+
3
b
+
5
)
l
S
+
l
H + lr + rIlI
(
3
a
+
b
+
4
)
l
S
+
l
r + rIlI
2
l
M
Computational cost
3
T
S
+
b
T
V
+
T
H
+
(
b
+
r
I
)
T
E
+
2
(
a
+
b
)
log
⁡
a
+
1
2
T
S
+
a
T
V
+
T
H
+
(
a
+
r
I
)
T
E
+
2
(
b
+
a
)
log
⁡
b
+
1
2
r
log
⁡
r
Transaction number
5
+
1
4
+
1
2Table 6
Comparison of properties.
Xie and Hengartner protocol [7]
Wang  et al. protocol [31]
Proposed protocol
Privacy preservation
√
√
√
Mutual authentication
√
√
√
Replay attack resistance
√
√
√
Non-TTP requirement
√
Nonidentity signer
√
Nonpersonal interest signer
√
Friendship relations
√
Friendship ownership certification
√


## 7. Implementation

In this work, we implement a simulation prototype based on our proposed schemes, including CredentialExchange (as shown in Figure2) and AuthObjectMatching (as shown in Figures 3 and 4), on mobile phones running the Android operating system.To implement our proposed scheme, we use two cell phones for each mobile system. The transmission interface is Wi-Fi. According to our proposed scheme, the prototype has two primary capabilities, credential exchange and mission matching. We assume CredentialExchange is finished via the implementation of Chiou and Huang [32]. In this phase, any two persons can exchange their credential to each other by using their cell phones. We implement AuthObjectMatching of MPM scheme. Anyone can recognize their common friends with other persons by using the credentials exchanged in CredentialExchange and find their matched target with each other by using the profile setup in AuthObjectMatching.Figure5 shows the Android mobile phone screens of our implementing prototype. We use JAVA program language to implement them. The types of equipment are Samsung Nexus S, which use Android 2.3 professional operation system. The technological specifications of the equipment are 16 GB ROM, 512 MB RAM, and Cortex-A8 1 GHz CPU, with WiFi network function.Initial screens of our implementation.
(a)
Splash screen
(b)
Meal matchmakingFirst of all, the splash screen is shown in Figure5(a), where we can see that it has the function to find a person to have meal with, to play game with, to see a movie with, or to do some other activities with. Clicking the button Meal proceeds to the next screen shown in Figure 5(b), where Server (CF)/Client (CF) denotes a server (initializer)/client (responder) choice with common friend function, and Server (NCF)/Client (NCF) stands for a server (initializer)/client (responder) choice without common friend function.Assume there are two persons who are going to find a person to have meal with via their mobile devices (as shown in Figure5(a)). After clicking the button Meal from the splash screen (as shown in Figure 5(b)), they can choose to be an initializer (or server) or responder (or client) with or without common friend function. Let the left device be a server by clicking Server (CF) button and the right one be a client by clicking Client (CF). Then, the screens of the two devices are shown in Figure 6(a). (If other buttons Server (NCF)/Client (NCF), instead of Server (CF)/Client (CF), are chosen, the scheme directly proceeds to set up personal and target profiles, as shown in Figure 7.)Server (a) and client (b) with common friend function.
(a)
Server sends message
(b)
Client returns messageSetup of personal and target profiles.
(a)
Server sends target profile
(b)
Client sends target profileThe two users then click Create Match Data to create their match datadm. After that, client clicks Listen Message to wait for the data-matching message dmserver from server and server clicks Send Message to send his message dmserver to client. After receiving the message, client clicks Check Common Friends button to check whether they have common friends.After that, as shown in Figure6(b), server clicks Listen Message to wait for the response of client, and client clicks Return Message to return its data-matching message dmClient to server. After that, server clicks Check Common Friends button to check whether they have common friends. If they have common friends, as shown in Figures 7(a) and 7(b), they can then set up their Personal Profile and Target Profile to see whether they find each other as their real target to have meal with.As shown in Figure7(a), client sets up his or her personal profile and clicks Listen Target Profile to see whether there is a response from server; server sets up his or her target profile and clicks Send Target Profile to send his/her target profile to client. If the personal profile and the target profile matche, server sets up his or her personal profile and clicks Listen Target Profile; client sets up his or her target profile and clicks Send Target Profile (as shown in Figure 7(b)).If the target profile of client matches the personal profile of server, client then clicks Listen Message to wait for the message from server (as shown in Figure8.) Server inputs some messages from Enter Message Here box and clicks Send Message to send the input message to client. Similarly, server clicks Listen Message to wait for the message from client. Client inputs some messages from Enter Message Here box and clicks Send Message to send the input message to server.Figure 8
Negotiation.By using the message exchange, server and client can negotiate for the meal time and place. Moreover, the exchanged message can be encrypted by a session key which can be encrypted by public keys. When the meeting time comes, server and client can authenticate each other via message authentication by the session key or by their public/private keys.


## 8. Conclusions

In this paper, we present MPM, a mobile matchmaking scheme, which is used not only to find a matched object but also to check whether a common friend exists. In the proposed scheme, privacy preservation, mutual authenticity, mutual friendship ownership certification, mutual prevention of friendship spoofing, and replay attack resistance are considered. Comparisons with other approaches show that the proposed schemes provide improved security while performing efficiently in terms of computational and communication costs. The implementation of the proposed algorithms on Android system mobile devices allows users to securely find a matched object.



---

*Source: 637985-2014-02-16.xml*