skip to main content
10.1145/2766498.2766501acmconferencesArticle/Chapter ViewAbstractPublication PageswisecConference Proceedingsconference-collections
research-article

How far removed are you?: scalable privacy-preserving estimation of social path length with Social PaL

Published: 22 June 2015 Publication History

Abstract

Social relationships are a natural basis on which humans make trust decisions. Online Social Networks (OSNs) are increasingly often used to let users base trust decisions on the existence and the strength of social relationships. While most OSNs allow users to discover the length of the social path to other users, they do so in a centralized way, thus requiring them to rely on the service provider and reveal their interest in each other.
This paper presents Social PaL, a system supporting the privacy-preserving discovery of arbitrary-length social paths between any two social network users. We overcome the bootstrapping problem encountered in all related prior work, demonstrating that Social PaL allows its users to find all paths of length two and to discover a significant fraction of longer paths, even when only a small fraction of OSN users is in the Social PaL system -- e.g., discovering 70% of all paths with only 40% of the users. We implement Social PaL using a scalable server-side architecture and a modular Android client library, allowing developers to seamlessly integrate it into their apps.

References

[1]
P. Aditya, V. Erdelyi, M. Lentz, E. Shi, B. Bhattacharjee, and P. Druschel. EnCore: Private, Context-based Communication for Mobile Social Apps. In MobiSys, 2014.
[2]
V. Arnaboldi, A. Guazzini, and A. Passarella. Egocentric Online Social Networks: Analysis of Key Features and Prediction of Tie Strength in Facebook. Elsevier Computer Communications, 36(10), 2013.
[3]
L. Backstrom, P. Boldi, M. Rosa, J. Ugander, and S. Vigna. Four Degrees of Separation. CoRR, abs/1111.4570, 2011.
[4]
B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 1970.
[5]
B. Cici, A. Markopoulou, E. Frias-Martinez, and N. Laoutaris. Assessing the Potential of Ride-sharing Using Mobile and Social Data: A Tale of Four Cities. In Ubicomp, 2014.
[6]
E. M. Daly and M. Haahr. Social Network Analysis for Routing in Disconnected Delay-tolerant MANETs. In MobiHoc, 2007.
[7]
E. De Cristofaro, P. Gasti, and G. Tsudik. Fast and Private Computation of Cardinality of Set Intersection and Union. In CANS, 2012.
[8]
E. De Cristofaro, M. Manulis, and B. Poettering. Private Discovery of Common Social Contacts. In ACNS, 2011.
[9]
M. J. Freedman and A. Nicolosi. Efficient Private Techniques for Verifying Social Proximity. In IPTPS, 2007.
[10]
M. J. Freedman, K. Nissim, and B. Pinkas. Efficient Private Matching and Set Intersection. In EUROCRYPT, 2004.
[11]
E. Gilbert. Predicting Tie Strength in a New Medium. In CSCW, 2012.
[12]
M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou. Walking in Facebook: A Case Study of Unbiased Sampling of OSNs. In INFOCOM, 2010.
[13]
M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou. Practical Recommendations on Crawling Online Social Networks. IEEE JSAC on Measurement of Internet Topologies, 2011.
[14]
D. Hardt. The OAuth 2.0 authorization framework. RFC 6749, RFC Editor, 2012.
[15]
Y. Huang, E. Chapman, and D. Evans. Privacy-preserving applications on smartphones. In HotSec, 2011.
[16]
P. Hui, J. Crowcroft, and E. Yoneki. Bubble Rap: Social-based Forwarding in Delay Tolerant Networks. In MobiHoc, 2008.
[17]
A. Johnson, P. Syverson, R. Dingledine, and N. Mathewson. Trust-based anonymous communication: Adversary models and routing algorithms. In CCS, 2011.
[18]
T. Kärkkäinen, M. Pitkänen, P. Houghton, and J. Ott. SCAMPI Application Platform. In CHANTS, 2012.
[19]
M. Lentz, V. Erdélyi, P. Aditya, E. Shi, P. Druschel, and B. Bhattacharjee. SDDR: Light-Weight, Secure Mobile Encounters. In USENIX Security Symposium, 2014.
[20]
J. Leskovec and C. Faloutsos. Sampling from Large Graphs. In KDSS, 2006.
[21]
M. Li, N. Cao, S. Yu, and W. Lou. FindU: Privacy-preserving personal profile matching in mobile social networks. In INFOCOM, 2011.
[22]
Q. Li, S. Zhu, and G. Cao. Routing in Socially Selfish Delay Tolerant Networks. In INFOCOM, 2010.
[23]
X. Liao, S. Uluagac, and R. A. Beyah. S-MATCH: Verifiable Privacy-preserving Profile Matching for Mobile Social Services. In DSN, June 2014.
[24]
G. Mezzour, A. Perrig, V. D. Gligor, and P. Papadimitratos. Privacy-Preserving Relationship Path Discovery in Social Networks. In CANS, 2009.
[25]
M. Miettinen, S. Heuser, W. Kronz, A.-R. Sadeghi, and N. Asokan. ConXsense: Automated Context Classification for Context-aware Access Control. In ASIACCS, 2014.
[26]
S. Milgram. The small world problem. Psychology Today, 67(1):61--67, 1967.
[27]
P. Mittal, M. Wright, and N. Borisov. Pisces: Anonymous Communication Using Social Networks. In NDSS, 2013.
[28]
M. Nagy, N. Asokan, and J. Ott. PeerShare: A System Secure Distribution of Sensitive Data Among Social Contacts. In NordSec, 2013.
[29]
M. Nagy, T. Bui, E. De Cristofaro, N. Asokan, J. Ott, and A.-R. Sadeghi. How Far Removed Are You? Scalable Privacy-Preserving Estimation of Social Path Length with Social PaL (Full Version). http://arxiv.org/abs/1412.2433, 2015.
[30]
M. Nagy, E. D. Cristofaro, A. Dmitrienko, N. Asokan, and A. Sadeghi. Do I know you? Efficient and Privacy-preserving Common Friend-Finder Protocols and Applications. In ACSAC, 2013.
[31]
G. Norcie, E. De Cristofaro, and V. Bellotti. Bootstrapping Trust in Online Dating: Social Verification of Online Dating Profiles. In USEC, 2013.
[32]
M. Sirivianos, K. Kim, J. W. Gan, and X. Yang. Assessing the veracity of identity assertions via OSNs. In COMSNETS, 2012.
[33]
M. Sirivianos, K. Kim, and X. Yang. SocialFilter: Introducing Social Trust to Collaborative Spam Mitigation. In CollSec, 2010.
[34]
C. Stocker. HHVM with Symfony 2 looks amazing. http://blog.liip.ch/archive/2013/10/29/hhvm-and-symfony2.html.
[35]
A. Tagliapietra. Symfony benchmark using HHVM. http://www.alexfu.it/2013/10/22/symfony-benchmark-on-hhvm.html.
[36]
A. S. Tanenbaum et al. Using Sparse Capabilities in a Distributed Operating System. In ICDCS, 1986.
[37]
J. Ugander, B. Karrer, L. Backstrom, and C. Marlow. The Anatomy of the Facebook Social Graph. CoRR, abs/1111.4503, 2011.
[38]
M. Von Arb, M. Bader, M. Kuhn, and R. Wattenhofer. VENETA: Serverless friend-of-friend detection in mobile social networking. In WiMob, 2008.
[39]
Y. Zhang, J. Zhao, and G. Cao. Roadcast: A Popularity Aware Content Sharing Scheme in VANETs. SigMobile Mob. Comput. Commun. Rev., 13(4), Mar. 2010.
[40]
J. Zhao and G. Cao. VADD: vehicle-assisted data delivery in vehicular ad hoc networks. In INFOCOM, 2006.

Cited By

View all

Index Terms

  1. How far removed are you?: scalable privacy-preserving estimation of social path length with Social PaL

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    WiSec '15: Proceedings of the 8th ACM Conference on Security & Privacy in Wireless and Mobile Networks
    June 2015
    256 pages
    ISBN:9781450336239
    DOI:10.1145/2766498
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

    Sponsors

    In-Cooperation

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 22 June 2015

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. mobile social networks
    2. privacy
    3. proximity

    Qualifiers

    • Research-article

    Conference

    WiSec'15
    Sponsor:
    • SIGSAC
    • US Army Research Office
    • NSF

    Acceptance Rates

    Overall Acceptance Rate 98 of 338 submissions, 29%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)12
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 18 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media