FindU: Privacy-Preserving Personal Profile
Matching in Mobile Social Networks
Ming Li*, Ning Cao*, Shucheng Yu+ and Wenjing Lou*
*Worcester Polytechnic Institute, Dept. of ECE
+University of Arkansas at Little Rock, Dept. of CS
IEEE INFOCOM 2011, Shanghai, China
April. 10 - 15, 2011
 Motivation
 Problem Formulation
Main Design
 Security Analysis
 Performance Evaluation
Mobile Social Network
 Mobile Social Networks (MSN): the proliferating of
mobile devices
– Location based services
– Augmented reality
– Making new connections using MSN
(profile matching)
Profile Matching in MSN
 Applications
Symptom matching in mobile health social network
Finding “familiar strangers” and initiate a small-talk
Finding likeminded vehicles on the road
Finding lost connections
Matched 1
{running, pingpong, swimming}
Matched 1
{running, tennis, golf}
Profile Matching in MSN (cont’d)
 Privacy issues
 User profiling: active or passive
 Individual privacy: get to know a specific user’s sensitive
attributes (e.g., a disease)
 Group privacy: malicious activities based on group attributes
(e.g., salesman from a pharmacy do marketing)
Goal: reveal only the necessary information to each other during
Existing Solutions
Directly publish and exchange the profile of each user
 MagnetU,
 E-Smalltalker [Yang, ICDCS 2010]
 Use hash table to encode user’s attributes; exchange hash table
 Suffers from dictionary attack – though can be salted to alleviate
 Same-symptom-based handshaking [Lu et. al., MONET 10]
 Establish a secret key only if two patients share exactly same
 Need semi-online trusted authority to distribute key material
 Uses pairing based cryptography- expensive
 Formulate the problem of privacy-preserving profile matching
in MSN (for the first time)
Three levels of privacy are defined
No central authority
 Propose two private set intersection schemes to achieve
increasing privacy, based on secure multiparty computation
(SMC) and secret sharing
Enhance the efficiency in computation & communication
Prove the security of the schemes, and evaluate performance
via simulations
 Motivation
 Problem Formulation
Main Design
 Security Analysis
 Performance Evaluation
 Network of N parties, P1 (initiator), P2, …, PN (candidates),
each with a set of attributes .
 Initiator wants to find out the “best match”, i.e., the party
with maximal
 Based on the intersection set with best match, P1 decides whether to
make connection.
 Communication is one-hop, all nodes are in rage; secure
pairwise communication channel exist already
 Security model: adversary is honest-but-curious, but can also
launch some active attacks; adversaries can collude.
Privacy Levels
 Level 1 privacy: P1 and each candidate only learn the
their intersection set:
, but adversary learns
nothing more beyond the output and its private input
 Level 2 privacy: P1 and each candidate only learn the size
of their intersection set:
 Level 3 privacy: P1 and each candidate only learn the
rank of the size of their intersection set:
 P1 is required to only connect with P* (best match)
and know their intersection set but not others, to
reveal least information about candidates.
 No central trusted authority
Need to achieve high security, while being fully distributed
 Resource constraint on mobile devices
 Existing works in SMC have high computational complexity
or communication overhead
 Existing cryptographic solutions are too expensive
 Private set intersection (PSI)
 Private cardinality of set intersection (PCSI)
 Motivation
 Problem Formulation
Main Design
 Security Analysis
 Performance Evaluation
Technical Preliminaries
 Shamir Secret Sharing Scheme: (t,w)-SS
Pick a random t degree polynomial
The secret is (or can be made) a number: D
 a0=D
 D1=q(1), ···, Di=q(i), ···, Dw=q(w)
Technical Preliminaries
 Secure Multiparty Computation based on SS
Homomorphic addition
Multiplication can be achieved via a two-round protocol
 Given shares
shares of
, i.e.
, the parties want to compute the
 Additive Homomorphic Encryption
To compute E(m1+m2), given
knowing the private key.
, without
The Basic Scheme
Express sets using polynomials
 P1 has
Pi has
 Pi’s set is expressed by coefficients of
 For each of P1’s attribute xj,
 Parties publish the shares of their attributes xj and polynomial
coefficients aik
The Basic Scheme
Parties will compute shares of
Rij - random numbers jointly generated by P1 and Pi not known by
 Using
- recall the two properties
2t+1 out of N parties need to be involved for P1 and Pi
 Enhancement is made during the SMC phase to lower the
communication cost
The Basic Scheme
Protocol is efficient in computation and communication
Result revealing:
 Values of {Fi(xj)}1≤j≤n remain in secret shared forms between
P1 and Pi before their shares are revealed to each other, to
provide verifiability
The Advanced Scheme
Parties first compute shares of
securely using the basic scheme
Must blind from P1 the correspondence
between its inputs and outputs - to achieve PL2
Idea: using a blind-and-permute (BP) method
 Employ additive homomorphic
 We reduce the number of invocations of
the BP protocol using share conversion
 Motivation
 Problem Formulation
Main Design
 Security Analysis
 Performance Evaluation
Complexity Analysis
 Computation and communication costs
t: maximum tolerated number of colluders
m: number of attributes of a candidate user
n: number of attributes used by the initiator (query)
N: total number of participants
Simulation Study
 Setup
Implement in NS2, since crypto libraries for SMC aren’t
available on smart phone yet
Assume 400MHz CPU and WIFI, and tell the simulator the
size of each group element, and the computation time of
each primitive
Estimated energy consumption using established models
for WiFi on cellphone platform.
Compared with FNP 04 (PCSI) and FC 10 (PSI) schemes.
Simulation Results
 Total run time
 Change n (number of attributes of P1)
 Change m (number of attributes of Pi)
Our schemes are more practical when the number of profile attributes is
large, while the number of query attributes is relatively small
Simulation Results
 Total run time
 Change N, fix t (collusion threshold)
 Change t, fix N (total number of parties)
Advantage of our proposed schemes: when n and N are both relatively small
(in the order of tens)
Security Comparison
Advantages of our schemes
Information-theoretic security for basic scheme under HBC
(honest-but-curious) model
Resist from active attacks
 We have formulated and addressed the privacypreserving profile matching problem in MSNs
 We used secure multiparty computation to achieve
desired security levels while using secret sharing to
reduce the computation overhead
 Simulation shows our protocols are suitable under
practical MSN scenarios – relatively small n and N, but
large m.
The End
Thank you!
Questions and Answer

similar documents