 Open Access
 Total Downloads : 4
 Authors : T . Lakshmi Sravanthi, V. Subhasini, P . Nageswara Rao, P . Ramewara Anand
 Paper ID : IJERTCONV2IS15040
 Volume & Issue : NCDMA – 2014 (Volume 2 – Issue 15)
 Published (First Online): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Gmatch: Secure and PrivacyPreserving Group Matching in Social Networks
T . Lakshmi Sravanthi1, V. Subhasini2, P . Nageswara Rao3, P . Ramewara Anand4
Department of Cse, Swethainstitute of Technology and Science::Tirupathi
AbstractGroups are becoming one of the most compellingfeatures in both online social networks and Twitterlike microblogging services. A stranger outside of an existing group may have the need to find out more information about attributes of current members in the group, in order to make a decision to join. However, in many cases, attributes of both group members and the stranger need to be kept private and should not be revealed to others, as they may contain sensitive and personal information. How can we find out matching information exists between the stranger and members of the group, based on their attributes that are not to be disclosed? In this paper, we present a new group matching mechanism, by taking advantage private set intersection and ring signatures. With our scheme, a stranger is able to collect correct group matching information while sensitive information of the stranger and group members are not disclosed. Finally, we propose to use batch verification to significantly improve the performance of the matching process.

INTRODUCTION
As online social networks and Twitterlike micro blogging services redefine our lifestyle, groups are becoming one of the most frequently used features. Groups are, in general, formed with common attributes, such as geographic locations and hobbies. However, the features of a group are generally described by only a few keywords or a short description, which sometimes is not enough for users to make decisions when choosing an appropriate group for themselves. Especially, when several groups have similar (or even the same) keywords and descriptions, it is very inconvenient for users to choose the most suitable one among these groups. In order to make a better decision when choosing a group to join, a stranger with a profile of his own attributes who is still an outsider of the group
needs to collect detail matching information from al l the group members' profiles. Such a problem is referred as to group matching.
In most situations, attributes of users are sensitive, such as personal health records and religious preferences. It is typical for a user to store these attributes privately [1], so that only his friends or members in the same group are able to reveal these attributes, but strangers or any third party cannot learn these sensitive information. Unfortunately, collecting group matching information using these sensitive attributes may introduce a number of privacy problems. On one hand, since the stranger is not familiar with the group, the stranger does not want to reveal his
sensitive attributes to any group member during the matching process. On the other hand, because the stranger is an outside and untrusted user to the group, each group member is reluctant to reveal his own attributes and the exact matching results between two entities to the stranger.
To make matters more challenging, each group member needs to generate a signature on his matching response, which contains matching information between the stranger and himself, and sends the signature and the matching response together to the stranger, so that the stranger is convinced the matching response is reliable and correct. Unfortunately, due to the unforgeability of signatures (only the entity with the knowledge of the private key can create valid signatures), the stranger is able to learn the identity of the signer on each matching response, and reveal exact matching information between himself and each group member.
In this paper, we proposed Gmatch, a novel secure and privacypreserving group matching scheme in online social networks. We utilize private set intersection [2] in Gmatch, so that the stranger is able to collect matching information from the group while both the stranger and each group member are able to preserve sensitive attributes to each other. Meanwhile, with ring signatures [3], [4], the stranger is convinced that matching information from the group is correct, but he cannot learn exact matching information between himself and each group member. In addition, we improve the efficiency of the matching process using batch verification.
The remainder of this paper is organized as follows: In Section II, we introduce the system model and design objectives. In Section III, we briefly describe cryptographic primitive s we utilized in Gmatch. We then present the details of Gmatch in Section IV. Section V provides a thorough security analysis, and Section VI evaluates the performance of Gmatch. Finally, we briefly discuss related work in Section VII, and conclude this paper in Section VIII.

PROBLEM STATEMENT

System Model
Our system is a social network, which includes a stranger S and all d group members P1, …, Pd in the group P (as shown in Fig. 1). The stranger S, who is not a member of the group P, has k attributes in his profile and the jth attribute is denoted as as,j . The stranger's profile is denoted as As = {as,1, …, as,k}. Group member Pi has m attributes
and the profile of this group member is denoted as Ai =
{ai,1, …, ai,m}. In our model, we assume all group members have the same size of profile. Attributes in every user's profile are private and sensitive, which are stored and maintained locally by each user. Note that we also assume there does not exist of a third party that first collects all the group members' profile s, and then simply completes group matching between itself and the stranger. Even if there exists a group manager who maintains basic activities of the group, such as the changes of membership, it is still not able to access sensitive attributes of group members. The stranger completes group matching in a distributed manner [5].
Fig. 1. Stranger S wants to collect group matching information from group P based on his attribute set AS.
During group matching, this stranger S wishes to collect group matching information from group P based on his profile. If an attribute in a group member's profile is equal to an attribute in the stranger's profile, it is then referred to as a matched attribute. Otherwise, it is called an unmatched attribute. The total number of group members that has the sameattribute with the attribute as,j , is denoted as the matchingdegree Djof attributeas,j. The group matching informationfrom the group P is described as D(P) = {D1, …, Dk}. Each group member Pi is asked to provide matching information to stranger S based on profile Ai, so stranger S can calculate group matching information D(P) from group P.

Privacy Threats
In this paper, we assume the stranger is honestbut curious. It means the stranger will honestly follow the protocol to collect group matching information, but may attempt to learn more information than allowed.

Design Objectives
During the group matching, our scheme should be able to provide the following desirable privacy properties. (1),Stranger's Attributes Privacy: The stranger does not revealany attribute in his profile to any group member. (2) GroupMembers' Attributes Privacy: The stranger only obtainsmatched attributes that both in his profile and some group member's profile, while the unmatched attributes in
group members' profiles are not disclosed to the stranger.
(3) ExactMatching Information Privacy: The stranger is able to compute groupmatching information, while any exact matching information between himself and each group member is not revealed.


PRELIMINARIES
In this section, we briefly introduce cryptographic primiti ves that we implement in Gmatch.

Bilinear Maps
Let G1, G2 and GT be three multiplicative cyclic groups of prime order p, g1 be a generator of G1, and g2 be a generator of G2. A bilinear map e is a map G1Ã— G2 GT with the following properties:

Computability: there exists an efficient algorithm for computing map e.

Bilinearity: for all

Nondegeneracy:e(g1, g2) 1.


Ring Signatures
The concept of ring signatures was first proposed by Rivest et al. in 2001 [3]. A ring signature scheme has the propertythat, a verifier is convinced that a ring signature was produc ed using one of group members' private keys, but this verifier is not able to determine which one.

Private Set Intersection
Private set intersection [2], [6], [7] enables two parties to calculate the intersection of their private sets without leaking any additional information. Private set intersection can be construct using additive homomorphic encryption, such as Paillier cryptosystem [8]. The additive homomorphic encryption algorithm Enc(Â·) in [8] is able to complete following operations, without knowing the corresponding plaintexts.

Given Enc(m1) and Enc(m2), output Enc(m1 + m2) = Enc(m1) Â· Enc(m2).

Given Enc(m1) and a constant c, output Enc(c Â· m1) = Enc(m1)c.


GMATCH: SECURE AND PRIVACY PRESERVING
GROUP MATCHING

Overview
In this section, we introduce Gmatch, a secure and privacypreserving group matching scheme. By utilizing private set intersection, the stranger can learn the matching information from the group without revealing any unmatched attributes in group members' profiles. With ring signatures, the stranger is convinced that a matching response is correct and generated by a group member, yet cannot distinguish this matching response belongs to which particular group member. Exploiting the properties of bilinear maps, Gmatch can support batch verification, which is able to greatly improve the efficiency of verification of ring signatures. In addition, with minor modifications in the construction of Gmatch, we can
achieve even higher privacy levels.

Gmatch
Gmatch includes four steps: Setup, Compute, Evaluate, Match. In Setup, strangerSand each group member generatetheir own public/private key pairs. In Compute, stranger S first generates a polynomial, where each attribute in his profile i s a root of this polynomial and all the roots are in his profile.
Then, stranger S encrypts all the coefficients of this poly nomial by performing additive homomorphic encryption, and sends all the encrypted coefficients to all the group members . In Evaluate, each group member evaluates a matching value for each attribute in his own profile using all the encrypted coefficients, signs a matching response that contains all th e matching values generated by himself, and sends this matching response and the corresponding signature to the stranger. In Match, strangerSfirst checks the correctness of a matchingresponse by verifying its signature, then computes whether each matching value in this matching response indicates a matched attribute. After collecting all the matching responses from all group members, the stranger S calculates matching degrees for all the attributes in his profile. Details of each step are listed as follows.
Setup.StrangerSgenerates his public/private key pair(pks, sks) for additive homomorphic encryption. Here, we utilize Paillier cryptosystem [8]. The encryption algorithm is denoted as Enc, and the corresponding decryption algorithm is denoted as Dec. Each group member generate his public/private key pair (pki, ski) for computing ring signatures. The ring signature scheme we used is BGLS [4], which is based on bilinear maps. The total number of group members is d. The number of attributes in the stranger's profile is k, and the number of attributes in each group member's profile is m.
Algorithm 1 KeyGen
Given two multiplicative cyclic groups G1, G2 with prime order p and their generators g1, g2 respectively, group member Pi generates his public key and private key as:

Pick random ui Zp.
2 2

Compute vi = g ui G .
Group member Pi's public key is pki = vi and his private key is ski = ui.
Compute.StrangerSfirst constructs akdegree polynomialP (x), whose k roots are all attributes in his profile. This polynomial is described as:
Clearly, if an attribute ai,j from group member Pi is a matched attribute that equals some attribute in stranger S's profile, then ai,j is also a root of this kdegree polynomial P (x), and we have P (ai,j ) = 0.
After generating polynomial P (x), stranger S encrypts all the k +1 coefficients of this polynomial P (x) using Enc with his public key pks. He then sends all the k + 1 encrypted coefficients {Enc(0), …, Enc(k)} to each group member (as illustrated in Fig. 2).
Evaluate.Group memberPihasmattributes and evaluates a matching value wi,j for each attribute ai,j in his profile. More specifically, group member Pi first computes an encrypted polynomial value Enc(P (ai,j )) for each attribute
Fig. 2. Stranger S sends all the encrypted coefficients to group member PI.
aij . Due to properties of additive homomorphic encryption we introduced in Section III, this encrypted polynomial value Enc(P (ai,j )) can be easily computed by Pi's attribute ai,j and all the encrypted coefficients Enc(i), for i [0, k], as follows:
Enc(P (ai,j ))
i,j
= Enc(0 + 1ai,j + Â· Â· Â· + kak )
= Enc(0) Ã— Enc(1)ai,jÃ— Â· Â· Â· Ã— Enc(k)aki,j . (2) After that, group member Pi generates a random number i,j
, and computes a matching value wi,j of attribute ai,j as: wi,j = Enc(i,jÂ· P (ai,j ) + ai,j )
= Enc(P (ai,j ))i,jÃ— Enc(ai,j ), (3)
where Enc(ai,j ) can be computed using the stranger's public key pks and attribute ai,j with Enc.
Then, group member Pi constructs his matching response wi = (wi,1, …,wi,m) using all his matching values, signs this matching response using ring signatures in Algorithm 2, and sends wi = (wi,1, …,wi,m) and its ring signature _i = (_i,1, …, _i,d) to stranger S (as shown in Fig. 3).
Algorithm 2 RingSign
Given all the group members public keys (pk1, …, pkd)
=(v1, …, vd), a matching response w, and a private key sks
= us for some s, this group member us

Randomly chooses yi 2 Zp and computes _i = gyi1 for all i 6= s and i 2 [1, d].

Computes h = H(w) 2 G1 and sets

Outputs the ring signature
Fig. 3. Group member Pi sends matching response wi and its signature _i to stranger S.
Match. Upon receiving a matching response wi and its ring signature _i, stranger S first verifies the correctness
of this matching response according to Algorithm 3. If the matching response passes the verification, stranger S decrypts each wi,j wi with decryption algorithm Dec. If the result of decryption matches one of his attributes, then ai,j is a matched attribute. Otherwise, it is an unmatched attribute. This is because
Dec(wi,j ) = Dec(Enc(i,jÂ· P (ai,j ) + ai,j ))
= i,j Â· P (ai,j ) + ai,j , (5) where P (ai,j ) = 0 and Dec(wi,j ) = ai,j , if ai,j As.
Algorithm 3 RingVerify
Given all the group members public keys (pk1, …, pkd)
=(v1, …, vd), a matching response w, and its ring signature
_ = (_1, …, _d), the stranger

Computes h = H(w) G1.

Verifies
If the equation holds, then this matching response is correct and signed by a group member. Otherwise, it is not.
After decryptingall the matching values from all the group members, stranger S is able to calculate the matching degree Dj , for j[1, k] and obtain group matching information D(P) = (D1, …,Dk) about this group P.



Batch Verification
Generally, the stranger in Gmatch has to verify d matching responses from all the d group members separately, which introduces prohibitive huge computation cost to himself. Utilizing properties of bilinear maps, the stranger can reduce the cost of verification by checking the integrity of all the matching responses in a batch manner, instead of verifying them one by one. The details of batch verification are shown in Algorithm 4.
Algorithm 4 BatchVerify
Given all the group members public keys (pk1, …, pkd) = (v1, …, vd), all the d matching responses (w1, …,wd), and
their ring signatures (_1, …,_d), where _i = (_i,1, …, _i,d), the stranger

Computes hl = H(wl)G1, for all l 2 [1, d].

Generates d random number (_1, …, _d) Zd p .

Verifies
e(dYl=1h_ll , g2)?=dYi=1e(dYl=1 ll,i , vi). (7)
If the equation holds, then all the matching responses are valid. Otherwise, they are not all valid.
Note that batch verification will fail if only one invalid matching response exists. To further detect a small number of invalid ones among all the responses, so the valid ones can still pass verification, we can leverage binary search
[9] during batch verification. More specifically, when batch verification fails, the stranger further divides the set of all the matching responses into two halves, and rechecks each half using batch verification. If one half passes, all the matching responses in this half are valid. Otherwise, two sub halves of this half will be further rechecked until all theinvalid ones are found.


Higher Privacy Levels
There are two ways to modify the construction of Gmatch, so that it can achieve even higher privacy levels. First, similar to the previous work [2], each matching value is computed as wi,j = Enc(_i,jP(ai,j)) instead of wi,j = Enc(_i,jP(ai,j))+ ai,j . Then, when the decryption result is 0, it means that there is a matched attribute in the group. However, the stranger cannot determine which particular attribute in his profile is matched to this attribute. Second, instead of signing the matching response wi, each group member signs each matching value wi,j 2 wi one by one using ring signatures, and sends each matching value separately to the stranger. Then, the stranger believes that every matching value is correct and signed by a group member, but cannot distinguish whether two different matching values are from the same group member. Further, the stranger cannot tell whether two different matched attributes are from the same group member. However, to achieve this higher privacy level, each group member has to operate m ringsigning operations instead of only one ringsigning operation, and the stranger also needs to verify mÃ—d ring signatures in total, which will increase the computation cost of the entire scheme.
In this section, we show that Gmatch is able to achieve the privacy properties we defined in Section II.
Theorem 1:Assuming that the additive homomorphic encryption is semantically secure, Gmatch achieves stranger'sattributes privacy.
Proof: In Gmatch, group member Pi obtains k + 1 encrypted coefficients of polynomial P(x) computed by additive homomorphic encryption algorithm Enc. If the additive homomorphic encryption Enc is semantically secure [8], it is computational infeasible for the group member to derive any plaintext when given only its corresponding ciphertext and public encryption key pks. Because Paillier cryptosystem, which we use in Gmatch, is semantically secure. Then, given encrypted coefficients
{Enc(_0), . . . , Enc(_k)} and public encryption key pks, group member Pi cannot learn {_0, . . . , _k} without the strangers private key sks. Further, group member Pi is not able to reconstruct the polynomial P(x) and compute all the k roots of P(x). Therefore, all the k attributes in stranger profile are not revealed to any group member, strangers attributes privacy is achieved.
Theorem 2: Assuming parameter _i,j for matching value wi,j is random, Gmatch achieves group members attributesprivacy.
Proof: According to Equation (5), the decryption result of matching value wi,j can be described as follows:
Clearly, when ai,j is a matched attribute, it is a root of polynomial P(x), then we have P(ai,j) = 0, and the decryption result is ai,j . When ai,j is an unmatched attribute, if _i,j is a random number, we have P(ai,j) 6= 0, and the decryption result is a random value. Therefore,
what the stranger obtains after decryption is either an attribute in his profile or a random value that does not disclose any unmatched attribute in any group members profile.
Theorem 3: Assuming each matching response is signed by ring signatures, then Gmatch achieves exact matchinginformation privacy with probability 1 1 /d, where d is the size of the group.
Proof: Due to the properties of ring signatures in BGLS [4], when verifying a matching response, the stranger is convinced that this matching response is signed by a group member but cannot distinguish which particular member it is from. The stranger can successfully distinguish that a matching response belongs to a particular group member with a probability of 1/d. Since the total number of matching responses received by the stranger is d, the total probability that the stranger successfully discloses the exact matching information between himself and every group member is 1/d. Therefore, Gmatch can achieve exact matching information privacy with probability 1 1 /d.
As we analyzed in Theorem 2, during the group matching, unmatched attributes in group members profiles are not disclosed to the stranger. However, by honestly following the group matching, the stranger can still obtain more information than allowed by performing all zero polynomial attacks [1]. More specifically, the stranger sets all k + 1 coefficients of polynomial P(x) as zeros. Under this type of attacks, the computation result of P(ai,j) is always zero, which makes the random number _i,j useless. Then, all the decryption results of matching values are attributes from one of group members profiles. In this case, the stranger is able to learn all the attributes in all group members profiles. Making matters worse, because the stranger only sends the encrypted coefficients to each group member, and the encryption algorithm is probabilistic, group members cannot check whether those coefficients are all zeros or not. To prevent this type of attacks, we set one of the k + 1 coefficients as 1, and is sent to group members without encryption. Similar methods can also be found in [1] [10]

PERFORMANCE
We now evaluate the efficiency of Gmatch in experiments by using the PBC library. All the experiments are tested on a 2.26 GHz Linux system. For the ease of implementation, we assume G1 = G2. The elliptic curve we used is an MNT curve with a base field size of 159 bits. The length of each element of G1 is p = 160 bits, and the length of an element of GT is 1024 bits. An encrypted coefficient under Enc is an element of Zn, where n = 2048 bits.

Efficiency of Gmatch: As we can see from Fig. 4(a), Fig. 5(a) and Fig. 6(a), the efficiency of group matching can be significantly improved by utilizing batch verification. More specifically, when the size of users profiles are fixed in Fig. 6(a), the rum time of Gmatch without batch verification exponentially increases with the total number of group members, while the one with batch verification only increases linearly with the group size.
The efficiency of group matching at each group member are illustrated in Fig. 4(b), Fig. 5(b) and Fig. 6(b). The run time at each group member in Gmatch is greatly increasing with the size of each roup members profile, but hardly
affected by the size of the strangers profile or the size of the group.

Efficiency of Batch Verification with Invalid Matching Responses: We now evaluate the performance of batch verificationunder different numbers of invalid matching responses.Clearly, the increasing number of invalid responses will reducethe efficiency of batch verification. In this experiment, we setthe total number of matching responses d = 100 and assume it always requires the worstcase algorithm to detect invalid ones from all the matching responses. As shown in Fig. 7, when less than
10% of all the matching responses are invalid, batch verification is still efficient than verifying them separately.


RELATED WORK

Twoparty private matching
Freedman et al. [2] proposed a private matching scheme, which allows a client and a server compute the set intersection with their own private sets. During private matching, the client only obtains the set intersection while the server does not know any matching result. Agrawal et al. [6] introduced a private matching scheme between two databases using commutative encryptions. Hazay and Lindell [7] exploited pseudo random functions to evaluate set intersection. In [11], DachmanSoled et al. exploited polynomial evaluations to compute the set intersection between two parties, and also leveraged Shamir secret sharing and cutandchoose protocol to improve efficiency. Recent work in [12] introduced an authorized private set intersection (APSI) based on blind RSA signatures. In APSI, each element in the clients set must be authorized by some mutually trusted authority.

Multiparty private matching
Kissner and Song [13] proposed a multiparty private matching scheme to compute the union, intersection and element reduction operations for multiple sets. However, this scheme requires a group decryption among multiple entities, which is impractical between the stranger and group members in social networks. Ye et al. [14] extended previous scheme to a distributed scenario with multiple servers. The dataset of the original server is shared by several subservers using (t,w) shamir secret sharing. Therefore, any t1 or fewer subservers cannot discover the dataset of the original server. Sang etal. [15] improved the efficiency of private matching among multiple parties by exploiting an extra N Ã— N nonsingular matrix, where N is the total number of entities. Li and Wu [10] proposed a private multiparty set intersection scheme based on the twodimensional verifiable secret sharing scheme.

Private matching in social networks
FindU [1] focuses on finding the best matched user from the group in mobile social networks. Yang et al. [16] introduced ESmallTalker, which allows users to privately match other people in mobile social networks using the iterative bloom filter (IBF) protocol.


CONCLUSION
In this paper, we proposed Gmatch, a secure and privacypreserving group matching in social networks. With Gmatch, the stranger can successfully collect group matching information while the private information of group members are preserved. Our experimental results show that Gmatch can efficiently compute correct group matching information with batch verification.
ACKNOWLEDGEMENT
We are grateful to the anonymous reviewers for their helpful comments. This work is supported by the National Science and Technology Major Project (No. 2012ZX03002003), Fundamental Research Funds for the Central Universities (No. K50511010001), National 111 Program (No. B08038), Doctoral Foundation of Ministry of Education of China (No. 20100203110002) and Program for Changjiang Scholars and Innovative Research Team in University.
REFERENCES

M. Li, N. Cao, S. Yu, and W. Lou, FindU: PrivatePreservi ng Personal Profile Matching in Mobile Social Networks, in Proc. IEEE INFOCOM, 2011, pp. 2435 2443.

M. J. Freedman, K. Nissim, and B. Pinkas, Efficient Private Matching and Set Intersection, in Proc. EUROCRYPT. Spring Verlag, 2004, pp. 119.

R. L. Rivest, A. Shamir, and Y. Tauman, How to Leak a Secret, in
Proc. ASIACRYPT. SpringerVerlag, 2001, pp. 552565.

D. Boneh, C. Gentry, B. Lynn, and H. Shacham, Aggregate an d Verifiably Encrypted Signatures from Bilinear Maps, in Proc. EUROCRYPT. SpringerVerlag, 2003, pp. 416432.

A. Sorniotti and R. Molva, Secret Interest Groups (SIGs ) in Social Networks with an Implementation on Facebook, in Proc. ACM SAC, 2010, pp. 621628.

R. Agrawal, A. Evfimievski, and R. Srikant, Information Sh aring Across Private Databases, in Proc. ACM SIGMOD, 2003, pp. 8697.

C. Hazay and Y. Lindell, Efficient Protocols for Set Inte rsection and Pattern Matching with Security Against Malicious and Covert Adversaries, in Proc. TCC. SpringerVerlag, 2008, pp. 155175.

P. Paillier, PublicKey Cryptosystems Based on Composit e Degree Residuosity Classes, in Proc. EUROCRYPT. SpringerVerlag, 1999,
pp. 223238.

C. Wang, Q. Wang, K. Ren, and W. Lou, PrivacyPreserving Public Auditing for Data Storage Security in Cloud Computing, in Proc. IEEEINFOCOM, 2010, pp. 525533.
pp. 125142.
[12]E. D. Cristofaro and G. Tsudik, Practical Private Set I ntersection Protocols with Linear Complexity, in Proc. FC, 2010, pp. 143159. [13]L. Kissner and D. Song, PrivacyPreserving Set Operat ions, inProc.CRYPT. SpringerVerlag, 2005, pp. 241257.
[14]Q. Ye, H. Wang, and J. Pieprzyk, Distributed Private Ma tching and Set Operations, in Proc. ISPEC. SpringerVerlag, 2008, pp. 347 360. [15]Y. Sang, H. Shen, Y. Tan, and N. Xiong, Efficient Protoco ls for Privacy Preserving Matching Against Distributed Datasets, in Proc. ICICS. SpringerVerlag, 2006, pp. 210227.Z. Yang, B. Zhang, J. Dai, A. C.Champion, D. Xuan, and D. Li, ESmallTalker: A Distributed Mobile System for Social Networking in Physical Proximity, in Proc. IEEE ICDCS, 2010, pp. 468 477.