skip to main content
10.1145/2523649.2523668acmotherconferencesArticle/Chapter ViewAbstractPublication PagesacsacConference Proceedingsconference-collections
research-article

Do I know you?: efficient and privacy-preserving common friend-finder protocols and applications

Published: 09 December 2013 Publication History

Abstract

The increasing penetration of Online Social Networks (OSNs) prompts the need for effectively accessing and utilizing social networking information. In numerous applications, users need to make trust and/or access control decisions involving other (possibly stranger) users, and one important factor is often the existence of common social relationships. This motivates the need for secure and privacy-preserving techniques allowing users to assess whether or not they have mutual friends.
This paper introduces the Common Friends service, a framework for finding common friends which protects privacy of non-mutual friends and guarantees authenticity of friendships. First, we present a generic construction that reduces to secure computation of set intersection, while ensuring authenticity of announced friends via bearer capabilities. Then, we propose an efficient instantiation, based on Bloom filters, that only incurs a constant number of public-key operations and appreciably low communication overhead. Our software is designed so that developers can easily integrate Common Friends into their applications, e.g., to enforce access control based on users' social proximity in a privacy-preserving manner. Finally, we showcase our techniques in the context of an existing application for sharing (tethered) Internet access, whereby users decide to share access depending on the existence of common friends. A comprehensive experimental evaluation attests to the practicality of proposed techniques.

References

[1]
Bandwagon. http://bandwagon.io.
[2]
Sidecar---My ride is your ride. http://side.cr/.
[3]
Zoosk. http://zoosk.com.
[4]
Agrawal, R., Evfimievski, A., and Srikant, R. Information sharing across private databases. In SIGMOD (2003).
[5]
Asokan, N., Dmitrienko, A., Nagy, M., Reshetova, E., Sadeghi, A.-R., Schneider, T., and Stelle, S. Crowdshare: Secure mobile resource sharing. In ACNS (2013).
[6]
Balfanz, D., Durfee, G., Shankar, N., Smetters, D. K., Staddon, J., and Wong, H.-C. Secret Handshakes from Pairing-Based Key Agreements. In S&P (2003).
[7]
Bellare, M. New proofs for NMAC and HMAC: Security without collision-resistance. In CRYPTO (2006).
[8]
Bellare, M., Namprempre, C., Pointcheval, D., and Semanko, M. The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme. Journal of Cryptology 16, 3 (2003).
[9]
Bellovin, S. M., and Cheswick, W. R. Privacy-Enhanced Searches Using Encrypted Bloom Filters. Tech. Rep. CUCS-034-07, Columbia University and AT&T, 2004. https://mice.cs.columbia.edu/getTechreport.php?techreportID=483.
[10]
Bloom, B. H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13, 7 (1970).
[11]
Camenisch, J., and Zaverucha, G. Private intersection of certified sets. In Financial Cryptography (2009).
[12]
Carter, H., Amrutkar, C., Dacosta, I., and Traynor, P. For your phone only: custom protocols for efficient secure function evaluation on mobile devices. Security and Communication Networks (2013).
[13]
Danezis, G., and Mittal, P. Sybilinfer: Detecting Sybil Nodes using Social Networks. In NDSS (2009).
[14]
De Cristofaro, E., Gasti, P., and Tsudik, G. Fast and Private Computation of Cardinality of Set Intersection and Union. In CANS (2012).
[15]
De Cristofaro, E., Kim, J., and Tsudik, G. Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model. In ASIACRYPT (2010).
[16]
De Cristofaro, E., Manulis, M., and Poettering, B. Private Discovery of Common Social Contacts. In ACNS (2011).
[17]
De Cristofaro, E., and Tsudik, G. Practical Private Set Intersection Protocols with Linear Complexity. In Financial Cryptography (2010).
[18]
De Cristofaro, E., and Tsudik, G. Experimenting with Fast Private Set Intersection. In TRUST (2012).
[19]
Dong, W., Dave, V., Qiu, L., and Zhang, Y. Secure friend discovery in mobile social networks. In INFOCOM (2011).
[20]
Eppstein, D., Goodrich, M. T., and Baldi, P. Privacy-Enhanced Methods for Comparing Compressed DNA Sequences. http://arxiv.org/abs/1107.3593, 2011.
[21]
Fischlin, M., Pinkas, B., Sadeghi, A.-R., Schneider, T., and Visconti, I. Secure Set Intersection with Untrusted Hardware Tokens. In CT-RSA (2011).
[22]
Fort, M., Freiling, F. C., Penso, L. D., Benenson, Z., and Kesdogan, D. TrustedPals: Secure Multiparty Computation Implemented with Smart Cards. In ESORICS (2006).
[23]
Freedman, M. J., Nissim, K., and Pinkas, B. Efficient Private Matching and Set Intersection. In EUROCRYPT (2004).
[24]
Hardt, D. The OAuth 2.0 authorization framework. RFC 6749, RFC Editor, 2012.
[25]
Hazay, C., and Lindell, Y. Constructions of truly practical secure protocols using standard smartcards. In CCS (2008).
[26]
Hazay, C., and Lindell, Y. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In TCC (2008).
[27]
Hohenberger, S., and Weis, S. Honest-Verifier Private Disjointness Testing Without Random Oracles. In PETS (2006).
[28]
Huang, Y., Chapman, E., and Evans, D. Privacy-preserving applications on smartphones. In HotSec (2011).
[29]
Huang, Y., Evans, D., and Katz, J. Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? In NDSS (2012).
[30]
Iliev, A., and Smith, S. More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties. Tech. Rep. TR2005-551, Dartmouth College, 2005.
[31]
Ioannidis, I., Grama, A., and Atallah, M. A Secure Protocol for Computing Dot-Products in Clustered and Distributed Environments. In ICPP (2002).
[32]
Jarecki, S., and Liu, X. Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection. In TCC (2009).
[33]
Jarecki, S., and Liu, X. Fast Secure Computation of Set Intersection. In SCN (2010).
[34]
Järvinen, K., Kolesnikov, V., Sadeghi, A.-R., and Schneider, T. Embedded SFE: Offloading Server and Network Using Hardware Tokens. In Financial Cryptography (2010).
[35]
Johnson, A., Syverson, P., Dingledine, R., and Mathewson, N. Trust-based anonymous communication: Adversary models and routing algorithms. In CCS (2011).
[36]
Kerschbaum, F. Public-key encrypted bloom filters with applications to supply chain integrity. In CODASPY (2011).
[37]
Kissner, L., and Song, D. X. Privacy-Preserving Set Operations. In CRYPTO (2005).
[38]
Kostiainen, K., Reshetova, E., Ekberg, J.-E., and Asokan, N. Old, new, borrowed, blue -- a perspective on the evolution of mobile platform security architectures. In CODASPY (2011).
[39]
Li, M., Cao, N., Yu, S., and Lou, W. FindU: Privacy-preserving personal profile matching in mobile social networks. In INFOCOM (2011).
[40]
Manulis, M., Pinkas, B., and Poettering, B. Privacy-Preserving Group Discovery with Linear Complexity. In ACNS (2010).
[41]
Mittal, P., Wright, M., and Borisov, N. Pisces: Anonymous Communication Using Social Networks. In NDSS (2013).
[42]
Mohaisen, A., Tran, H., Chandra, A., and Kim, Y. Trustworthy distributed computing on social networks. In ASIACCS (2013).
[43]
Nagy, M., Asokan, N., and Ott, J. PeerShare: A System Secure Distribution of Sensitive Data Among Social Contacts. In NordSec (2013).
[44]
NIST. http://www.nsa.gov/ia/_files/nist-routines.pdf.
[45]
Norcie, G., De Cristofaro, E., and Bellotti, V. Bootstrapping Trust in Online Dating: Social Verification of Online Dating Profiles. In USEC (2013).
[46]
Rantala, E., Karppanen, A., Granlund, S., and Sarolahti, P. Modeling energy efficiency in wireless Internet communication. In MobiHeld (2009).
[47]
Recordon, D., and Reed, D. OpenID 2.0: a platform for user-centric identity management. In DIM (2006).
[48]
Tanenbaum et al., A. S. Using Sparse Capabilities in a Distributed Operating System. In ICDCS (1986).
[49]
Thiagarajan, N., Aggarwal, G., Nicoara, A., Boneh, D., and Singh, J. P. Who killed my battery?: Analyzing mobile browser energy consumption. In WWW (2012).
[50]
Von Arb, M., Bader, M., Kuhn, M., and Wattenhofer, R. VENETA: Serverless friend-of-friend detection in mobile social networking. In WiMob (2008).
[51]
Yao, A. C. How to Generate and Exchange Secrets. In FOCS (1986), pp. 162--167.
[52]
Zhang, L., and Li, X.-Y. Message in a Sealed Bottle: Privacy Preserving Friending in Social Networks. http://arxiv.org/abs/1207.7199, 2012.
[53]
Zhang, R., Zhang, Y., Sun, J., and Yan, G. Fine-grained private matching for proximity-based mobile social networking. In INFOCOM (2012).

Cited By

View all
  • (2024)Friendship jealousy and interaction needs: how mutual friend features affect users of WeChat MomentsFrontiers in Psychology10.3389/fpsyg.2024.141103415Online publication date: 9-Oct-2024
  • (2024)New Approach for Efficient Malicious Multiparty Private Set IntersectionInformation Sciences10.1016/j.ins.2024.120995(120995)Online publication date: Jun-2024
  • (2023)A Practical Multiparty Private Set Intersection Protocol Based on Bloom Filters for Unbalanced ScenariosApplied Sciences10.3390/app13241321513:24(13215)Online publication date: 13-Dec-2023
  • Show More Cited By

Index Terms

  1. Do I know you?: efficient and privacy-preserving common friend-finder protocols and applications

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Other conferences
        ACSAC '13: Proceedings of the 29th Annual Computer Security Applications Conference
        December 2013
        374 pages
        ISBN:9781450320153
        DOI:10.1145/2523649
        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

        • ACSA: Applied Computing Security Assoc

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        Published: 09 December 2013

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. access control
        2. privacy enhancing technologies
        3. social networks

        Qualifiers

        • Research-article

        Funding Sources

        Conference

        ACSAC '13
        Sponsor:
        • ACSA
        ACSAC '13: Annual Computer Security Applications Conference
        December 9 - 13, 2013
        Louisiana, New Orleans, USA

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

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

        Other Metrics

        Citations

        Cited By

        View all
        • (2024)Friendship jealousy and interaction needs: how mutual friend features affect users of WeChat MomentsFrontiers in Psychology10.3389/fpsyg.2024.141103415Online publication date: 9-Oct-2024
        • (2024)New Approach for Efficient Malicious Multiparty Private Set IntersectionInformation Sciences10.1016/j.ins.2024.120995(120995)Online publication date: Jun-2024
        • (2023)A Practical Multiparty Private Set Intersection Protocol Based on Bloom Filters for Unbalanced ScenariosApplied Sciences10.3390/app13241321513:24(13215)Online publication date: 13-Dec-2023
        • (2022)Tag-Based Verifiable Delegated Set Intersection Over Outsourced Private DatasetsIEEE Transactions on Cloud Computing10.1109/TCC.2020.296832010:2(1201-1214)Online publication date: 1-Apr-2022
        • (2022)HERB+: Evolving an Industrial-Strength Privacy-Preserving Machine Learning Framework2022 IEEE 27th Pacific Rim International Symposium on Dependable Computing (PRDC)10.1109/PRDC55274.2022.00035(212-223)Online publication date: Nov-2022
        • (2022)Privacy-Preserving Negotiation of Common Trust Anchors Across Blockchain Networks2022 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)10.1109/ICBC54727.2022.9805532(1-5)Online publication date: 2-May-2022
        • (2020)Attribute-Based Fine-Grained Access Control for Outscored Private Set Intersection ComputationInformation Sciences10.1016/j.ins.2020.05.041Online publication date: May-2020
        • (2020)Two-Sided Malicious Security for Private Intersection-Sum with CardinalityAdvances in Cryptology – CRYPTO 202010.1007/978-3-030-56877-1_1(3-33)Online publication date: 17-Aug-2020
        • (2019)Faster fog-aided private set intersectionwith integrity preservingFrontiers of Information Technology & Electronic Engineering10.1631/FITEE.180051819:12(1558-1568)Online publication date: 10-Jan-2019
        • (2018)Labeled PSI from Fully Homomorphic Encryption with Malicious SecurityProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243836(1223-1237)Online publication date: 15-Oct-2018
        • Show More Cited By

        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